Do you really need to read() all of that?

Theo Jepsen <tjepsen@wisc.edu>

A contrived example

struct Record {
    int id;
    char name[32];
};
struct Record records[NUM_RECORDS];

for (int i = 0; i < NUM_RECORDS; i++)
    read(fh, &records[i], sizeof(struct Record));

for (int i = 0; i < NUM_RECORDS; i++)
    if (records[i].id == 7)
        printf("%s\n", records[i].name);

• Are all the bytes actually accessed?

Outline

• Introduction
• I/O data-flow analysis tool
• Byte classification
• File slicing
• Conclusions

I/O data-flow analysis tool

• Based on Pin, Intel's dynamic binary instrumentation tool
• Mark bytes read from a file as tainted
  • e.g. read(fh, buff, 3); (buff+0, buff+1, buff+2 are now tainted)
• Maintain mapping of tainted memory addresses to source bytes in file
  • e.g. 0x123abc -> file.txt:37
• Log every access to a tainted byte:
  • is taint being spread?
  • what's the type of instruction?

Example program: summing two bytes

• file.bin:

  $ xxd file.bin 
  0000000: 0102                                     ..

• Test program:

  char a, b;
  read(fd, &a, 1);
  read(fd, &b, 1);
  
  char x = a + b;

Example program: parsing XML

• file.xml:

  <A>
    <B>7</B>
    <C x="2"></C>
  </A>

• Test program:

  $ xmllint --xpath "//A/B/text()" file.xml
  7

Which instructions access which bytes?

key1=value1
key2=value2
needle=haystack
foo=bar

What can we observe about the bytes?

• Bytes flow together with contiguous bytes
  • e.g. the bytes in 'key1' flow together
• Bytes flow to same locations in memory
  • e.g. adding numbers, pointer arithmetic
• Bytes are accessed by a subset if instructions
  • e.g. some bytes flow to a jnz instruction
• Bytes flow out of program (e.g. syscall)

Byte classification: k-means clustering

What features can we use for clustering?

• # of destinations in program memory
• # of instructions
• # of branch instructions
• # of TEST/CMP instructions
• # of ADD/SUB/MUL instructions
• # of MOV instructions
• # of SYSCALL instructions

Cluster #0 [ 'k e y 1', 'k e y 2', 'f o o', 'b a r' ]
Cluster #1 [ '=', '0xa', '=', '0xa', '=', '0xa', '=', '0xa' ]
Cluster #2 [ 'v a l u e 1', 'v a l u e 2', 'n e e d l e', 'h a y s t a c k' ]

Slicing

slicing is a method for automatically decomposing by analyzing their data flow and control flow. Starting from a subset of a program's behavior, slicing reduces that to a minimal form which still produces that behavior. The reduced , a "slice," is an independent guaranteed to represent faithfully the original within the domain of the specified subset of behavior.

Weiser, Mark. "Program slicing." Proceedings of the 5th international conference on Software engineering. IEEE Press, 1981.

Uses of file slicing

• Measuring read() efficiency -- what % of bytes are used?
  • minimizing file to bytes necessary for a particular program
• Classifying types of data in a file
• Testing: crafting partially valid, yet incomplete test inputs
• Debugging: which byte in the file broke my code?
• Analyzing performance: measuring the overhead of using different types of files

Measuring read() efficiency: results

• Unzip a single file: unzip archive.zip a.txt
• Get a value from GDBM DB: ./gdbm-get-value key database.gdbm
• SQLite query: SELECT * FROM Track WHERE TrackId=1337
• Print EXIF headers: jhead img.jpg

$ unzip -l archive.minimized.zip
Archive:  archive.minimized.zip
  Length      Date    Time    Name
---------  ---------- -----   ----
       33  12-05-2015 13:52   a.txt
     7524  12-05-2015 14:48   LICENSE
---------                     -------
     7557                     2 files

$ unzip archive.minimized.zip a.txt
Archive:  archive.minimized.zip
  inflating: a.txt                   

$ unzip archive.minimized.zip
Archive:  archive.minimized.zip
  inflating: a.txt                   
file #2:  bad zipfile offset (local header sig):  95

Future work

• Collect data from more types of programs and files
• Control dependence: which paths are taken because of a byte?
• Data dependence: which bytes in the file depend on each other?
• How about other types of I/O? Network?
• What is the relationship between file slices?
  • fs₁ ∪ fs₂
  • fs₁ ∩ fs₂
  • fs₁ ∖ fs₂
  • fs₁ ⊂ fs₂

So maybe you don't need to read() all of that!

Get your head out of those books and stop read()ing all those pages, you bookworms.

Any questions about...

• The I/O data-flow analysis tool
• Classifying bytes in a file
• File slicing, and its uses
  • minimizing a file

Explore more programs here: http://pages.cs.wisc.edu/~tjepsen/fileslice/