Wednesday, July 31, 2013

Using symbolic execution to solve a tiny ASCII maze.

In this post we'll exercise the symbolic execution engine KLEE over a funny ASCII Maze (yet another toy example)!


Maze dimensions: 11x7
Player pos: 1x1 Iteration no. 0
Program the player moves with
a sequence of 'w', 's', 'a' or 'd'
Try to reach the prize(#)!
           |X|     |#|
           | | --+ | |
           | |   | | |
           | +-- | | |
           |     |   |
The match is between a tiny maze-like game coded in C versus the full-fledged LLVM based symbolic execution engine, KLEE.

How many solutions do you think it has?

The Maze

The thing is coded in C and the impatient can download it from here. This simple ASCII game asks you first to feed it with directions. You should enter them as a batch list of actions. As "usual"; a is Left, d is Right, w is Up and s is Down. It has this looks ...
Player pos: 1x4
Iteration no. 2. Action: s.
|X|     |#|
|X| --+ | |
|X|   | | |
|X+-- | | |
|     |   |
It's really small I know! But the code hides a nasty trick, and at the end, you'll see, it has more than one way to solve it.


KLEE is a symbolic interpreter of LLVM bitcode. It runs code compiled/assembled into LLVM symbolically. That's running a program considering its input(or some other variables) to be symbols instead of concrete values like 100 or "cacho". In very few words, a symbolic execution runs through the code propagating symbols and conditions; forking execution at symbol dependant branches and asking the companion SMT solver for path feasibility or counter-examples. For more info on this check out this, this or even this. Find it interesting? Keep reading!

Wednesday, July 24, 2013

Autocad DWG-AC1021 Heap Corruption

AutoCAD is a software for computer-aided design (CAD) and technical drawing in 2D/3D, being one of the world leading CAD design tools. It is developed and sold by Autodesk, Inc.
  • Title: AutoCAD DWG-AC1021 Heap Corruption
  • CVE Name: CVE-2013-3665
  • Permalink:
  • Advisory:
  • Patch:
  • Vendor notified on: 2013-03-27
  • Patch/Fix Released: 2013-07-10
  • Advisory Published: 2013-07-24

AutoCad is vulnerable to an arbitrary pointer dereference vulnerability, which can be exploited by malicious remote attackers to compromise a user’s system. This issue is due to AutoCad’s failure to properly bounds-check data in a DWG file before using it to index and copy heap memory values. This can be exploited to execute arbitrary code by opening a specially crafted DWG file, version AC1021.

This version was the native fileformat of AutoCAD Release 2007. New versions of the format emerged but AC1021 is still supported in modern AutoCADs for back ward compatibility.


The DWG R2007 file format The R2007 dwg format has sections and pages. There are system sections and data sections. The system sections contain information about where the data sections and their pages are in the file. The system sections are built based in two main data structures: a first header and a second header. In addition, there are two important sections in the file structure, the page map and the section map. Each one of this sections should be decoded using Reed Solomon algorithm and also could be compressed with a proprietary algorithm (which we will ignore). The file structure looks like this:
The DWG R2007 also known as AC1021 is well documented by the reversing effort of opendesign.

Vulnerability Details

Not surprisingly AutoCAD starts by parsing the 1st header. Among other things it reads the size and location of the 2nd header. Then from the second header it reads the position in the file where the page map is stored, the number of pages present in the file (page-count) and the maximum id (page-max-id ) a page shall have. The page map is stored in a single system section page and it is composed by tuples (Id, Size) where the Id is the page number. After the loading of the page map, begins the processing of the section map that eventually will load all the objects present in the draw. Graphically the data representing the page map on the file looks like this:
When each PageMap node is read two data structures are updated, a double linked list of page map nodes called PMapList and an id indexed array of node pointers called PMapArray. A quick description of this three entities follows.

The page map nodes

In memory the structure holding a page map node has the following fields:
  • acc: Accumulator of the field size (64 bits)
  • size: Size of the page. (64 bits)
  • id: Number of the page. (64 bits)
  • prev: Address in memory of the previous node. (32 bits)
  • next: Address in memory of the next node.(32 bits)
  • unknown: there are 2 unknown fields of 64 bits (Not used).

The page map linked list

And they are linked in the PMapList that looks like this:

The page map array

PMapArray is an array of node pointers maintained for quick access of the page map nodes. It maps the id to the actual page map node. A memory chunk of pages-maxid size is allocated for it as declared in the 2nd header.

The bug

When each new page map node is created its address is stored in the corresponding id position of the PMapArray array without checking its boundaries. Thus, enabling an arbitrary heap offset overwrite with a pointer to the recently created node. Details on the exploitation technique can be found in Joshep white paper or in the actual proof of concept exploit.