Could a computer program given the source or object version of another program be used to automate testing for trapdoors/backdoors?
It depends on what your requirements are.
A sufficiently complex and well-designed system could be used to identify the most simple backdoors or trapdoors in most programming languages. However, if a language is Turing complete, any single expression or function can be expressed in an infinite number of ways, which makes such analysis equal to the halting problem.
A quick example of this is adding
All of these are equal, and there are an infinite number of other ways to perform the same calculation. This gets even more complex when there are different instructions that can be used to do (almost) the same thing.
Most current vulnerability analysis that focuses on static analysis of executables works by identifying compiler artefacts, i.e. oddities and idiosyncrasies of individual compilers that allow for signature-based matching of potentially vulnerable code fragments. However, the automated tools spit out a large number of false positives, so a skilled person still has to sift through the results.
Since a backdoor is an is not a defined artefact, i.e. a backdoor may exist in a whole variety of different forms (e.g. backdoor account, reverse shell, hidden files, etc.), it is even more difficult to identify such problems. If the backdoor is something like an intentional buffer misuse to allow for easy buffer overflow exploitation, then it may well be possible to detect such a problem. If it's something more complex, like a particular secret command used to disable file access control, then it's nearly impossible.
|show 5 more comments|
What can theoretically be done is to provide, for a given application, a formal definition of its exact functionality, and then a formal proof (verifiable by a computer) that the application really fulfills that definition. This cannot be slapped on an existing program in all generality (see the Halting Problem: even when the functionality is "ultimately halts", it cannot be proven true or proven false for all programs). However, this can be done with the help of the programmer or his compiler.
Very reduced versions of that exist, e.g. bytecode for a Java Virtual Machine. The functionality is there "does not write outside a buffer, does not call an inexistent method on an object" (that's a gross simplification, of course). When the JVM loads the code, it "proves" that this functionality is respected. This works with a conceptually simple flow analysis and it works because the Java compiler took care to produce code for which the flow analysis works (in recent versions, the compiler even includes hints which the JVM just has to check rather than recompute).
Ideally, we would want a formal specification which captures more user-level semantics. This leads to three issues:
If we can do all three, then we can write applications which are provably non-malicious. As a side effect, we also prove that the applications are bug-free. This alone shows that it is not easy.
Some people are working on it. Don't hold your breath, though.
No. It is beyond the state of the art to automatically detect malicious backdoors in your code.
Sure, you could write a code-scanning tool to look for some specific known backdoor. But the problem is that there are too many ways an attacker could introduce a backdoor, and it is not feasible to identify all such patterns. In fact, if you think about it a little bit, you will quickly see that -- in the general case -- verifying the absence of backdoors is as difficult as verifying the correctness of the code, which is beyond the state of the art for most software systems we build today.
There are deep reasons to believe that finding malicious backdoors automatically is difficult, based upon a reduction to the halting problem. However, the practical barriers are even more serious. As a result, at the moment, there is no good, reliable way to automatically scan a program and determine whether it contains a malicious backdoor or not.
TL;DR: Yes, but it depends on what you mean by
I will start by proposing specific definitions to some of the above terms, partly because the previous answers referred to different meanings, and partly to make it easier to follow the discussion.
Before I continue, it is important to note that according to this definition of "Backdoor",
Of course there are others, though not infinite; if the (mis)functionality can be designed, it can be analyzed, but let's start with these, for now.
Now, once we've defined the functionality (irrelevant of the implementation) that we'd like to find, let's describe what a possible program+ruleset would look like, to find such (mis)functionality.
Obviously, such a scanner could not work by scanning the code for specific patterns and signatures, since there is an infinite number of ways to implement a given functionality.
Rather, for a scanner to succeed in this, it would have to perform a form of compilation, analyzing both the data flow (between inputs, variables, parameters, outputs, etc) and the control flow (e.g. what influences when to branch, what other functions to call, how to loop, etc.), and also correlations between them (e.g. branching depending on the result of a calculation based on input).
Now, if we could script our own ruleset, it would be possible to find any flow, that succeeds in passing the authentication mechanism, without a valid comparison between the username which came from the userinput and a value from the database, AND a valid comparison between the password which came from userinput and a value from the database.
In a similar manner, we can do the same for authorization bypass: declare the authorization mechanism, then find places where this is subverted or bypassed by the username or identity (which is actually also influenced by the username...). Also, we would need to find places where there is NO access check, but sensitive / suspicious actions are performed.
Thus, given the existance of such a scanning platform, and the effort to script our ruleset, we can absolutely find any unauthorized functionality (my definition of the problem).
For example, if we now want to check that the programmer did not embed some code which includes a block of encrypted instructions whose key is derived from various system parameters, such that the actual backdoor is hidden - we could easily script a rule that finds any place that the code decrypts a block, then dynamically executes this. Sure, it might be possible that there will be a false positive - perhaps if there is some strange, unique functional requirement to actually do this (really?) - but these can be adjusted for, and then scan the original code pre-encryption.
So, bottom line - Is it possible to scan source code for a given class of backdoor?
Will this typically provide a 100% guarantee, with mathematical proof?
If one examines a blackbox (non-opensource) software, treating it only as a blackbox, i.e. providing some input data and analysing the outputs, then IMHO it is intuitively evident that there is barely chance that any sufficiently intelligently implanted backdoors could ever be detected. For instance the software may contain a "timed bomb", i.e. it does something particular when a certain praticular time comes but otherwise behaves entirely normally as one expects. Several decades ago I happened to know of such a timed bomb: The computer (mainframe) of a firm crashed almost every other day during the night time and an employee who was the system specialist had to come and work hard to bring up the system again. After sometime the management noticed the importance of this guy for the firm and promoted him to the chief of the computing centre. After that the usual crash at night "mysteriously" disappeared.
There are commercial analyzers that work on compiled binaries, e.g Veracode and Fortify.
Of course, because of the halting problem, if they do not find anything, it does not mean there are no trapdoors.