Scenario

You are a cyber forensic investigator. You obtain a criminal's computer, and locate a suspicious program. When you scan the program with an anti-virus program, it reports nothing. Then, you look at the binary, you find that the code is obfuscated and all the constant strings are somewhat unnatural (doesn't look like normal strings). You look at closer, you find out that whenever the program is using the string, there is a common code snippet used to modify the string before it is used. For example, "fopen( decode( "some_weird_text"), ... ." You realize that by applying the same logic of the "decode()" function, you can successfully decode "some_weird_text." However, you find that there are so many those strings (e.g., more than a thousand strings are like that), making it difficult to do automatically.

This assignment asks you to (1) locate those weird strings, (2) identify the function like "decode" that would give you instructions how to decode the weird strings, (3) construct a logic from the logic of the identified "decode()" function, and (4) apply the logic and decode the strings.

An Example

Consider the following program:

char g_szTemp[1024];

extern "C" char* decode(char* s)

{

  strcpy( g_szTemp, s );

  for( int i = 0; i < 200; i++ ) {

   if( g_szTemp[i] != 0 ) {

    g_szTemp[i] -= 5;

   }

  }

  return g_szTemp;

}

int main()

{

 system(decode("r{%~tzwdknqj%4ij{4szqq"));

 return 0;

}

The program has a system() function call that runs a shell command. Typically, one may use the function like system("ls -l") to execute a shell command: "ls -l".

However, in this example, we do not see a string that looks like a command. Of course, to know how it works, you can run the program and observe what it wants to execute. Unfortunately, running a suspicious program on a machine is highly dangerous. Imagine a binary with a lot of obfuscated code and strings. A safe option would be running it on a VM. However, that would be significantly slower.

In practice, a static analysis would be used to handle this type of malware. Specifically, static analysis does not run the program. It analyzes program code to find out what the program would do. In our case, we can develop a static analysis tool that finds out all the encoded strings and decode them.

In this example, we will use LLVM to develop a static analysis tool that can find out all strings and how they are encoded, eventually revealing real strings hidden in the program.

How?

The below is a LLVM IR for the main function

@.str = private unnamed_addr constant [23 x i8] c"r{%~tzwdknqj%4ij{4szqq\00", align 1

; Function Attrs: uwtable

define i32 @main() #2 {

entry:

  %retval = alloca i32, align 4

  store i32 0, i32* %retval

  %call = call i8* @decode(i8* getelementptr inbounds ([23 x i8]* @.str, i32 0, i32 0))

  %call1 = call i32 @system(i8* %call)

  ret i32 0

}

The analysis starts from the @.str that holds a suspicious string. By checking instructions that use the string, we identify the decode function:

  %call = call i8* @decode(i8* getelementptr inbounds ([23 x i8]* @.str, i32 0, i32 0))

Note that later the return of the decode function is used in the system() in the next line. Hence, we can know that the decode function's return will be a decoded string.

Now, look at the decode function.

; Function Attrs: nounwind uwtable

define i8* @decode(i8* %s) #0 {

entry:

  %s.addr = alloca i8*, align 8

  %i = alloca i32, align 4

  store i8* %s, i8** %s.addr, align 8

  %0 = load i8** %s.addr, align 8

  %call = call i8* @strcpy(i8* getelementptr inbounds ([1024 x i8]* @g_szTemp, i32 0, i32 0), i8* %0) #4

  store i32 0, i32* %i, align 4

  br label %for.cond

for.cond:                                         ; preds = %for.inc, %entry

  %1 = load i32* %i, align 4

  %cmp = icmp slt i32 %1, 200

  br i1 %cmp, label %for.body, label %for.end

for.body:                                         ; preds = %for.cond

  %2 = load i32* %i, align 4

  %idxprom = sext i32 %2 to i64

  %arrayidx = getelementptr inbounds [1024 x i8]* @g_szTemp, i32 0, i64 %idxprom

  %3 = load i8* %arrayidx, align 1

  %conv = sext i8 %3 to i32

  %cmp1 = icmp ne i32 %conv, 0

  br i1 %cmp1, label %if.then, label %if.end

if.then:                                          ; preds = %for.body

  %4 = load i32* %i, align 4

  %idxprom2 = sext i32 %4 to i64

  %arrayidx3 = getelementptr inbounds [1024 x i8]* @g_szTemp, i32 0, i64 %idxprom2

  %5 = load i8* %arrayidx3, align 1

  %conv4 = sext i8 %5 to i32

  %sub = sub nsw i32 %conv4, 5

  %conv5 = trunc i32 %sub to i8

  store i8 %conv5, i8* %arrayidx3, align 1

  br label %if.end

if.end:                                           ; preds = %if.then, %for.body

  br label %for.inc

for.inc:                                          ; preds = %if.end

  %6 = load i32* %i, align 4

  %inc = add nsw i32 %6, 1

  store i32 %inc, i32* %i, align 4

  br label %for.cond

for.end:                                          ; preds = %for.cond

  ret i8* getelementptr inbounds ([1024 x i8]* @g_szTemp, i32 0, i32 0)

}

The first things to observe is to identify what is the return value.

for.end:                                          ; preds = %for.cond

  ret i8* getelementptr inbounds ([1024 x i8]* @g_szTemp, i32 0, i32 0)

As you can see, it returns g_szTemp.

Now lets see how the g_szTemp is used. At the beginning of the function, the argument is copied to g_szTemp via strcpy.

; Function Attrs: nounwind uwtable

define i8* @decode(i8* %s) #0 {

entry:

  %s.addr = alloca i8*, align 8

  %i = alloca i32, align 4

  store i8* %s, i8** %s.addr, align 8

  %0 = load i8** %s.addr, align 8

  %call = call i8* @strcpy(i8* getelementptr inbounds ([1024 x i8]* @g_szTemp, i32 0, i32 0), i8* %0) #4

  store i32 0, i32* %i, align 4

  br label %for.cond

Then, there are 2 places that the g_szTemp is used.

for.body:                                         ; preds = %for.cond

  %2 = load i32* %i, align 4

  %idxprom = sext i32 %2 to i64

  %arrayidx = getelementptr inbounds [1024 x i8]* @g_szTemp, i32 0, i64 %idxprom

  %3 = load i8* %arrayidx, align 1

  %conv = sext i8 %3 to i32

  %cmp1 = icmp ne i32 %conv, 0

  br i1 %cmp1, label %if.then, label %if.end

and

if.then:                                          ; preds = %for.body

  %4 = load i32* %i, align 4

  %idxprom2 = sext i32 %4 to i64

  %arrayidx3 = getelementptr inbounds [1024 x i8]* @g_szTemp, i32 0, i64 %idxprom2

  %5 = load i8* %arrayidx3, align 1

  %conv4 = sext i8 %5 to i32

  %sub = sub nsw i32 %conv4, 5

  %conv5 = trunc i32 %sub to i8

  store i8 %conv5, i8* %arrayidx3, align 1

  br label %if.end

The first code block only reads the g_szTemp. Hence, it does not decode.

The second block (if.then:) has load => sub => store, which is a sequence of transforming the data. Looking at the sub instruction, one can see that it does g_szTemp[i] = g_szTemp[i] - 5 for decoding.

Note that here,

  %4 = load i32* %i, align 4

  %idxprom2 = sext i32 %4 to i64

shows that it loads "i". To make sure that the transformation is applied to every bytes, one needs to see the range of i.

Looking at the code that initialize i and branches,

  store i32 0, i32* %i, align 4

  br label %for.cond

for.cond:                                         ; preds = %for.inc, %entry

  %1 = load i32* %i, align 4

  %cmp = icmp slt i32 %1, 200

  br i1 %cmp, label %for.body, label %for.end

...

for.inc:                                          ; preds = %if.end

  %6 = load i32* %i, align 4

  %inc = add nsw i32 %6, 1

  store i32 %inc, i32* %i, align 4

  br label %for.cond

The range of i can be identified: 0 to 199.

LLVM Tool

The above procedure shows the manual inspection and analysis. Our goal is to automate this and make an LLVM tool that can extract how the program decode.

Assumptions

Building a complicated static analysis tool requires a lot of time. In this assignments, we will make a few assumptions to make your life easy.

Assumptions are as follows:

(1) Decoding functions all have the name "decode".

(2) Encoded strings are all global variables. And all global constant strings are encoded.

(3) The decode function's first argument is a global constant string and its return is a decoded string.

What to extract from the program?

To understand the decoding logic from the program, there are a few things that you need to extract from the program.

(T1) Given a decode function, you need to find out what are the input string of the decode function, and what are the variables that are copied, and how they are related to a return value.

(T2) Between the input and the return value, there will be computations. You will identify them to understand what to decode.

(T3) Range of variable and pattern of the variable.

Let's take an example:

extern "C" char* decode(char* s)

{

  strcpy( g_szTemp, s );

  for( int i = 0; i < 200; i++ ) {

   if( g_szTemp[i] != 0 ) {

    g_szTemp[i] -= 5;

   }

  }

  return g_szTemp;

}

In the above code, the transformation formula is "decode[i] = encode[i] - 5"

To know this, (T1) s is copied to g_szTemp and then it goes through the above computation and then returned.

In addition, to identify the computation you need to know the computation: g_szTemp[i] -= 5 (which is (T2)).

Finally, you need to understand the values that i can hold. By looking at the for loop. 0 < i < 200. Moreover, i++ shows that i will be 0, 1, 2, ... 200. (which is (T3)).

With those information, you can safely say that the decoding procedure can be given an input string, you can apply the extracted computation (-= 5) (T2), on every single byte of the input (T3).