Could a computer program be used to automate testing for trapdoors?

Question

Could a computer program given the source or object version of another program be used to automate testing for trapdoors/backdoors?

Answer 1

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 a and b together, to produce c.

c = a + b
c = (-a) - (-b)
c = (a - 1) + (b + 1)
c = ((a * 2) + (b * 2)) / 2

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.

Answer 2

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:

• It is difficult to distinguish between malicious and non-malicious code. Is deleting a file a malicious action ? Yes, except if that's what the user wanted. Translating the user whims into a formal specification looks like a quite daunting task.

• The specification should follow a mathematical structure which is amenable to automatic verification. The Halting Problem looms nearby.

• The programmer should be able to efficiently turn the specification into some code which is provable and still runs at reasonable speed.

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.

Answer 3

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.

Therefore, the standard approach today is to rely upon your trust in the folks who wrote the program. If the program comes from someone who you trust won't attack you (e.g., Microsoft, Apple, assuming you trust them), then you can run it and rely upon your trust in the source of the program. This approach leads to relying upon branding or individuals who you have a relationship with. Alternatively, if you don't trust the source of the program, then your choices are to either run it and take a risk, or else run it in a sandbox that restricts what the program can do. The latter leads to sandboxed execution platforms, like web browsers provide for running Javascript (since in general there's no reason to trust the web site that sent you the Javascript, the only safe option is to run the Javascript in a sandbox that sharply limits what it can do, so that malicious backdoors are limited in the harm they can cause). These approaches have their own limitations, but given the state of the art, they're the most realistic defense today.

Answer 4

TL;DR: Yes, but it depends on what you mean by computer program, source or object version, automate, testing and backdoors.

---

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.

• Computer program: In order to remain completely vendor-agnostic, let us assume that there is such a product that would allow us to program our rules, and have that applied to the target code. This would need to function in a specific form, see below, but let's assume such a product exists.
• Source or object version: I will discuss source code analysis here; in theory, it should be possible to decompile the binary object format into source code, and continue from there. However, I have never tested this part, nor am I familiar with any product that would do this cleanly. So, source code is a requirement for this answer.
• Automated: While I would expect such a program to scan man thousands and millions of lines of code automatically, without manual intervention, I am not requiring this to be 100% automated straight out of the box, nor do I expect the program to have a generic answer for ALL target programs. Rather, I will allow manual configuration / tweaking / scripting, before running the full scan.
• Testing: The purpose here is to find existing backdoors - not necessarily 100%, and not to mathematically prove there are no others, but to find as many as possible, such that it provides a high level of confidence. Just like XSS scanners attempt to find most such flaws, but with no mathematical guarantee it is complete. Moreover, the level of confidence is directly correlated to the threat model - treat each class of backdoor as a threat, then we can scan for those (regardless of the implementation). If you haven't modeled it - it won't be found.
• Backdoor: From OWASP's definition: Malicious code inserted into a program for the purposes of providing the author covert access to... the program.
  Specifically, I am NOT including in this any form of "backdoor software", i.e. trojan horses or any other malware, such as BackOrifice; I am NOT including system-level backdoors, such as a hidden OS user; I am NOT including anything framework-level or compiler-based, such as Ken Thompson's classic Unix compiler rootkit; and I am NOT including cryptographic trapdoors such as the Debian flaw. I am only talking about code level backdoors (otherwise scanning code for them is irrelevant, anyway).
  I am also very specifically NOT including general security vulnerabilities; as @D.W. put it in a comment: backdoors (deliberately introduced by a developer) vs. vulnerabilities (inadvertently introduced by developers). Or even simpler: Unauthorized functionality.
  For the sake of my explanation, I will also not be referring to untrusted client apps; it will be simpler to discuss only the case of large, enterprise server systems, wherein the threat is that one of the many developers of the system, inserted unwanted functionality, to allow himself "covert access". However, this can be easily transferred later to client and/or 3rd party apps, too.

Before I continue, it is important to note that according to this definition of "Backdoor", testing for backdoors is nearly meaningless, without some additional definition. (It would be akin to saying "test for all bugs" - you need to scope which forms of bugs you expect to find. Or as the PHB said to Dilbert: I need to know all the unexpected things that can go wrong.) Now, I am not claiming merely that we should explicitly describe the backdoor, and then we can find it; but I mean that there are a certain number of classes of backdoors, and we will be able to scan for any defined class of backdoor (for which there is an infinite number of possible implementations, of course).
For example, here are a few classes of backdoors, classified by (mis-)functionality:

• Authentication bypass (via special user / "magic number" or parameter / hidden URL)
• Authorization bypass (via special user / hidden parameter)
• Data access via backend leakage (i.e. sending the data outside of the protected database, e.g. emailing credit card numbers).

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).
Additionally, it must be possible for us to define, tailored for each target program we're scanning, how to find certain global, well-defined elements of the application. For example, What object or method represents authentication checks? This could be as simple as an object/method name, or more complex to even heuristics; but for now, let's say we can specify the authentication mechanism's name. Same thing for how the application accesses the database (in the designed, legitimate fashion).

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 other words, what we're looking for is a flow that matches these conditions: ( (pass-authentication) && !( (input.username == database.username) && (input.password == database.password) ) ) (in very pathetic pseudocode...) Of course, the values might be checked in SQL, or first pulled from the database and checked in application code...
(We also need to adjust for password encryption, which can be solved the same as before, and hey while we're at it let's check that passwords ARE encrypted, otherwise throw a vulnerability...)
Basically, we just found all cases where it is possible to "authenticate" without sending a valid username and password. Problem solved.

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.
Backend data stealing: define the sensitive data (e.g. passwords; credit card numbers, etc.); find any place that data flows to an external target (e.g. via email, network access, files, etc) besides the database. Note that we may need to finetune this, according to the application - perhaps there is an MQ server to copy everything to a mainframe... But we can simply exclude those too, just as we excluded the database. Also note that these should be known to the architect.

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).

---

FOOTNOTE:
However, you might now raise the objection: "Well, sure, but you only defined a small subset of the possible backdoors".
Actually, while this might be true in a strict sense, it is not in a practical manner, at least according to our previous definitions.
At a very high level, there are a very limited ways of achieving access to the program - and while I did not mention all of them, the list is not long. Remember, we're not looking for any hidden functionality, only those that provide access at a code level.
Furthermore, if any other form of backdoor is deemed relevant, according to the application's threat model / risk profile, that form can similarly be analyzed and scripted for.

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?
Yes. The problematic part is in defining the classes of backdoors which are relevant.

Will this typically provide a 100% guarantee, with mathematical proof?
No. Then again, the same applies for any other type of vulnerability scanner (e.g. scanning source code for XSS), but depending on the amount of effort we can get incrementally and xenomorphically closer to 100%, such that it is good enough.

Answer 5

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.

Answer 6

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.