Stealth Back-doors

General Back-doors

One of the most under-estimated attack methods for computer applications is constituted of alternative ways by which an unauthorized third party causes undesired side-effects or breaches. Reliability is conferred by two factors which cannot be clearly delimited: developer trust in respecting the specification and developer intention for correct behaviour. This thin line occurs as of the human inability to account for an exhaustive set of cases (mistakes) and deliberate harm for personal or organizational interests. This problem propagates as an issue of trust between software vendor and client or open-source developer and user. A back-door could be hidden inside the kernel or even inside the CPU or anywhere else in all the machinery involved in running a process.

This report addresses the issue in the open-source pool of programs due to usage considerations and efficiency of distribution, even from untrusted sources. However, our findings open up a whole new attack vector reliant on compiler back-doors which can affect any vertical of the economy and pose threats to the security of critical computing infrastructures.

Compiler based back-doors

What if neither static nor dynamic analysis can detect undesired behaviour in all instances of the verification process? They cannot, unless the analysis method considers a specific compiler(e.g. DFA on code generated by some version of a compiler) and that compiler generates code that the analysis can account for (e.g. the generated code causes a wrong memory access violation which KLEE can detect).

The main problem is that when code is correct, the compiler breaks the correctness by miscompiling it. Existing verification tools typically focus on the source program, not on the generated binary. As a result, code that is verified to be correct may still have a backdoor. This is really bad!

But how can one know which compiler to use for building a project? The latest? Or one that has not been released long ago? Research in compiler testing[1] proves to be effective (i.e., helps find bugs, but it is not efficient). Choosing the right compiler remains an open-ended problem which one could exploit for inserting back-doors in software products.

According to Chris Wysopal[2], back-doors can be split into three types:

System Back-doors

Give root access to the system. The Case Study on vsftpd, an FTP server, presents how a previous vulnerability in a released version was turned into a compiler-based backdoor
Credential Back-doors

Allow authentication through slight changes of the supplied username and password. This type of attack could be easily detected on a rigorous analysis, but with the compiler-based approach the chances of detection significantly decrease.
Crypto Back-doors

This type of back-door is meant to weaken the cryptographic scheme used, perhaps through a level out of random bit patterns in cryptographic keys, which can make an attack less computationally intensive. We describe this prospective idea in Section 5, with GNU PG still under consideration.

How to create a back-door?

For compiler-based back-doors, the most important step is to target a compiler bug. Most of the released open-source compilers have been robustly tested, so there is a small probability that the code snippet that triggers the bug would not obfuscate the attacked software product. It is important to exclude any kind of undefined behaviour, which can be grasped from [3] and [4]. The back-door lies in the software patch to be submitted for revision, which contains the bug trigger. The C language gives rise to many opportunities for a creative bug insertion through macros, pragmas and keywords, all in the name of optimization.

Compiler Bugs for GCC

Our relevant case studies are based on compiler bugs found using the tool called Csmith[1], which generates C programs of a specific pattern to stress-test compilers.

Before designing any exploit, it is essential to understand the bug and to isolate the least number of lines of code that trigger the bug. Both GCC and LLVM, two popular C compilers, were analyzed. GCC bugs were used for exploits in particular.

GCC Bug 42721

Description

The function foo can be replaced by a macro or an inline function. The bug is triggered when the constant folding takes place: the expression (foo (a, -1ULL) != 1L) is folded to 0 for most values of a

The buggy gcc function does the following and it is called from fold_div_comapre: add two doubleword integers with doubleword result. Return nonzero if the operation overflows according to UNSIGNED_P. Each argument is given as two ‘HOST_WIDE_INT’ pieces. One argument is L1 and H1; the other, L2 and H2. The value is stored as two ‘HOST_WIDE_INT’ pieces in *LV and *HV.

From the documentation of fold_div_compare(): Subroutine of fold() that optimizes comparisons of a division by a nonzero integer constant against an integer constant, i.e. X/C1 op C2.

CODE is the comparison operator: EQ_EXPR, NE_EXPR, GT_EXPR, LT_EXPR, GE_EXPR or LE_EXPR.

Why is add_double_with_sign called?

x/c1 != c2  
=> x - (c1 * c2) > (c1 - 1)  
for unsigned values   
=> (c1 * c2) and (c1 * c2) + (c1 - 1)  
checked for overflow   
=> buggy_gcc_function called  
=> check for overflow using the macro:  
#define OVERFLOW_SUM_SIGN(a, b, sum) \
        ((~((a) ^(b)) & ((a) ^(sum))) < 0)

Reported behaviour

$ current-gcc -O1 small.c -o small
$ ./small
checksum = 1 (CORRECT)
$ current-gcc -O2 small.c -o small
$ ./small
checksum = 0 (WRONG)

Snippet

static unsigned long long foo (unsigned long long x,
                               unsigned long long y)
{
  return x / y;
}
static int a, b;

int main (void)
{
  unsigned long long c = 1;
  b ^= c && (foo (a, -1ULL) != 1L);
  if (b != 1)
    __builtin_abort ();
  return 0;
}

Affected versions

Version	Target	OS	Optimization Level
gcc 4.5.0 20100112 (experimental), revision r155838	i686-pc-linux-gnu	Ubuntu 9.10	Wrong code at -O2
gcc 4.4	i686	N/A	Wrong code at -O2
gcc 4.3	i686	N/A	Wrong code -O0 vs -O1
gcc 4.3.0 shipped by Fedora	i686	Fedora 9	Wrong code in all cases
gcc 4.4.3 shipped by Fedora	i686	Fedora 9	Wrong code at -O2

Bug fix

CVS: Revision r155887
Git: https://github.com/gcc-mirror/gcc/commit/7fa61d419d766c2b06f204a08a0b205ed91d1735

GCC Bug 43438

Description

There is a cast from unsigned char (type of l_11) int when the copy is made for the function argument. The argument is sign-extended. The pattern can be: any assignment of an unsigned char or function call where the formal parameter is an int but the actual one is an unsigned char.

l_11 must be assigned the value 254 directly or through constant propagation.

Reported behaviour

$ current-gcc -O0 small.c -o small -Wall
$ ./small
1 (CORRECT)
$ current-gcc -O1 small.c -o small -Wall
$ ./small
0 (WRONG)

Snippet

/* As produced by Csmith */
extern int printf (__const char *__restrict __format, ...);

static unsigned char g_2 = 1;
static int g_9;
static int *l_8 = &g_9;

static void func_12(int p_13)
{
  int * l_17 = &g_9;
  *l_17 &= 0 < p_13;
}

int main(void)
{
  unsigned char l_11 = 254;
  *l_8 |= g_2;
  l_11 |= *l_8;
  func_12(l_11);
  printf("%d\n", g_9);
  return 0;
}

Affected versions

Version	Target	OS	Optimization Level
4.2.4, 4.3.4, 4.4.3	i?86--, x86_64--	N/A	Wrong code for -O1
4.5.0 20100314 (experimental)	i686-pc-linux-gnu	N/A	Wrong code for -O1
X86: Revision r157445
X64: Revision r157542

Bug fix

CVS:

On 4.5 branch: Revision r157592
On 4.4 branch: Revision r157634
On 4.3 branch: Revision r158555

Git:

On 4.5 branch: https://github.com/gcc-mirror/gcc/commit/0895c53c41cfab6c1522b9b02ad9edb35b6724f2
On 4.4 branch: https://github.com/gcc-mirror/gcc/commit/6def23561816ef0154f6748bfe2dccfeae4455a7
On 4.3 branch: https://github.com/gcc-mirror/gcc/commit/bc14d9070289e9e5a08a920ad7043defefce977f

GCC Bug 42952

Description

Generally, in C, a static variable must be initialized with a constant (const qualifier does not count) i.e literals or expressions that evaluate to constants (e.g. if we have const int N = 5; we cannot say static int g[1] = N).

The sequence of assignments must be preserved, but there may be intermediate instructions (declarations, assignments, arithmetic operations, function calls).

Reptorted behaviour

$ current-gcc -O small.c -o small
$ ./small
1 (It should print 0)

Snippet

/*Types for which the bug is reproduced:
    (A)i >= 1 int g[i] */
/* Types for which the bug is NOT reproduced: struct */
static int g[1];

static int *p = &g[0];
static int *q = &g[0];

int foo (void)
{
   g[0] = 1;
   // Dead store elimination removes critical instruction. Alias identified as RO.
   *p = 0;  
   *p = *q;
   return g[0];
}  

int main()
{
   printf ("%d\n", foo());
   return 0;
}

Affected versions

Version	Target	OS	Optimization Level
4.3.4, 4.4.2	N/A	N/A	Dead store elimination for -O and -O -fno-tree-pta
4.5.0 20100204	i?86--, x86_64--	N/A	-fno-tree-ccp -fno-tree-fre
(experimental)
Revision: r156486

Bug fix

CVS:

On trunk: r156494
On branch 4.4: r156495
On branch: 4.3: r156496

Git:

On trunk: https://github.com/gcc-mirror/gcc/commit/76e2bdc62116c24c5da783360d0a2d5653a3ebea
On branch 4.4: https://github.com/gcc-mirror/gcc/commit/89411a3727643674aad382605e350b5cfae423bc
On branch 4.3: https://github.com/gcc-mirror/gcc/commit/2618aa95ba8dcafc466437b2b26be734e9a6fa1a

GCC Bug 43360

Description

Loop optimization pass determines that *p is invariant with value x + 7 and hoisted it in front of the loop, while retaining a dataflow fact indicating x + 7 == y + 7, which no longer held after code motion. [Yang, Xuejun et al. “Finding and understanding bugs in C compilers.” PLDI (2011).]

Reported behaviour

$ current-gcc -O1 small.c -o small
$ ./small
11   (CORRECT)
$ current-gcc -O2 small.c -o small
$ ./small
8     (WRONG)

Snippet

/* Adaptation from Csmith program */

/* Both variables must be global */
int x = 4;
int y[1][1];


void foo (void)
{
   /* for can be substituted with while */
   for (y[0][0] = 1; y[0][0] < 8; y[0][0]+=7) {
       int *p = &y[0][0];
       *p = x;
   }
}

int main (void)
{
  foo ();
  printf("%d\n", y[0][0]);
  return 0;
}

Affected versions

Version	Target	OS	Optimization Level
gcc 4.5.0 20100112 (experimental), Revision r157445	i686-pc-linux-gnu	N/A	Wrong code at -O2
gcc 4.4	x86-64--, i?86--	Linux	Wrong code at -O2

Bug fix

CVS:

On trunk: r157539
On branch 4.3: r157540
On branch 4.4: r157541

Git:

On trunk: https://github.com/gcc-mirror/gcc/commit/2521c0845d8e7b2718a0d50afab07989a98a0893
On branch 4.3: https://github.com/gcc-mirror/gcc/commit/95166ecd94aa7dee7421309f190934ed8594985b
On branch 4.4: https://github.com/gcc-mirror/gcc/commit/f11bf2ae0bd106ad4e94ce60e10523712c1f549d ```

GCC Bug - GCC Summit #1 - Exposing Difficult Compiler Bugs With Random Testing, Regehr, John et al., GCC Summit 2010

Reported behaviour

Should print 1. GCC r164319 at -O2 on x86-64 prints “0”

Snippet

[static] int x; /* Not necessarily static */
// Volatile pointer (rarely used!)
[static] int *volatile z = &x; /* Not necessarily static */

/*Function must be static */
static int foo (int *y) {
   /* printf of *y gives segmentation fault in the buggy compiler only */
   return *y;
}

/* Wikipedia: volatile keyword indicates that a value may
   change between different accesses, even if it does not
   appear to be modified. This keyword prevents an optimizing
   compiler from  optimizing away subsequent reads or writes
   and thus incorrectly reusing a stale value or omitting writes. */
int main (void) {
   *z = 1;
   printf ("%d\n", foo(&x));
   return 0;
}

GCC Bug - GCC Summit #2 - Exposing Difficult Compiler Bugs With Random Testing, Regehr, John et al., GCC Summit 2010

Reported behaviour

Should return 0. GCC 4.2.3 from Ubuntu Hardy (8.04) for x86 returns 1 at all optimization levels.

Snippet

int foo (void) {
    signed char x = 1;
    unsigned char y = 255;
    return x > y;
}

GCC Bug 57124

Description

The compiler does not cast x7 to unsigned when performing the unsigned comparison. This results in the true branch being executed (4294705142 <= 268435455U), which is wrong.

Behaviour exhibited in revision r198413 using -O2 -fno-strict-overflow [-ffast-math -march=corei7], where the bracketed flags are optional. The behaviour does not occur with -fwrapv.

Snippet

__attribute__ ((noinline))
foo(short unsigned int [*]p1, short unsigned int [*]p2)
{
  [short unsigned int x1, x4;]
  int [x2, x3, x5,] x6;
  unsigned int x7;

 /* Not necessary sequence of assignments. */
  x1 = *p1;
  x2 = (int) x1;  // The cast zero-extends 0xfffb
  x3 = x2 * 65536;
  x4 = *p2;
  x5 = (int) x4;  
  x6 = x3 + x4;
 /* Instead, the sequenced can be written as: */
  x6 = ([*]p1 * 65536) + [*]p2

  /* Does not work if x6 substituted by a constant. */
  x7 = (unsigned (int | long | long long)) x6;
  /* x6 = 0xfffbfff6; in decimal -262,154 */
  /* x7 = 0xfffbfff6; in decimal 4,294,705,142 */

  /* C unsigned comparison: if one operand is unsigned, the other operand
     is converted to unsigned, making, for example, -1 > 2U true. */
  if (x7 <= 268435455U)
     abort ();
  exit (0);
}

int main()
{
  short unsigned int x, y;
  x = -5;
  y = -10;
  /* x = 0x0000fffb and y = 0x0000fff6 */
  foo ([&]x, [&]y);
  return 0;
}

Triggering a bug

The bugs presented above manifest only in some environments, as presented in the table under Affected Versions, for each bug. The environments were created using Docker, which allows independent light-weight “containers” to run within a single Linux instance, avoiding the overhead of starting and maintaining virtual machines [7]. The main approach was to build a Docker image with the appropriate GCC version corresponding to a bug. Building GCC from source required an outdated OS version, of which we have have chosen CentOS 6, which comes with GCC 4.4.7 in its Development Tools Package.

Isolating patterns

Injecting the compiler bugs as illustrated previously is not feasible, as they need to merge with the rest of the target program. Slight changes of the examples (e.g., adding/removing variables) reveal how they could be manipulated and still trigger the bug. To reach the purpose of a clean back-door injection, the analysis of the bugs isolates patterns that would still trigger the bug (See comments for GCC bugs). A larger class of programs to be used for a back-door is thus created.

References

[1] Xuejun Yang, Yang Chen, Eric Eideand John Regehr. 2011. Finding and understanding bugs in C compilers. In Proceedings of the 32nd ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI ’11). ACM, New York, NY, USA, 283-294.
DOI=http://dx.doi.org/10.1145/1993498.1993532
Tool Web Page:
https://embed.cs.utah.edu/csmith/ [Accessed August 24, 2017]

[2] Scott Berinato, Application Security: Is the Backdoor Threat the Next Big Threat to Applications?, December 18, 2007
Web Page: http://www.csoonline.com/article/2122126/application-security/application-security–is-the-backdoor-threat-the-next-big-threat-to-application.html [Accessed August 23, 2017]

[3] John Regehr, A Guide to Undefined Behavior in C and C++, Parts 1, 2 and 3 Posted on July 9, 2010, July 23, 2010 and July 30, 2010
Web Page: https://blog.regehr.org/archives/213 [Accessed August 24, 2017]

[4] Xi Wang, Nickolai Zeldovich, M. Frans Kaashoek, Armando Solar-Lezama: Towards optimization-safe systems: analyzing the impact of undefined behavior. SOSP 2013: 260-275

[5] Shakespeare of Programming, Re-building a vsFTPd backdoor exploit in Python, May, 5 2016
Web Page: https://0x00sec.org/t/re-building-a-vsftpd-backdoor-exploit-in-python/159 [Accessed August, 24 2017]

[6] Schneier, Security Pitfalls in Cryptography, Information Management & Computer Security, 1998
Web Page: https://www.schneier.com/essays/archives/1998/01/security_pitfalls_in.html [Accessed August, 24 2017]

[7] ’Docker(software)’, in Wikipedia: The Free Encyclopedia, Wikimedia Foundation Inc.
Web page: https://en.wikipedia.org/wiki/Docker (software)
[Accessed September, 16 2017]

Compiler-based Back-doors - Part I

Stealth Back-doors

General Back-doors

Compiler based back-doors

How to create a back-door?

Compiler Bugs for GCC

GCC Bug 42721

Description

Reported behaviour

Snippet

Affected versions

Bug fix

GCC Bug 43438

Description

Reported behaviour

Snippet

Affected versions

Bug fix

GCC Bug 42952

Description

Reptorted behaviour

Snippet

Affected versions

Bug fix

GCC Bug 43360

Description

Reported behaviour

Snippet

Affected versions

Bug fix

GCC Bug - GCC Summit #1 - Exposing Difficult Compiler Bugs With Random Testing, Regehr, John et al., GCC Summit 2010

Reported behaviour

Snippet

GCC Bug - GCC Summit #2 - Exposing Difficult Compiler Bugs With Random Testing, Regehr, John et al., GCC Summit 2010

Reported behaviour

Snippet

GCC Bug 57124

Description

Snippet

Triggering a bug

Isolating patterns

References