Additional Guidelines and Suggestions forProject Milestone 1CS161 Computer Security, Spring 2008Some students may be a little vague on what to cover in the Milestone 1submission for the course project, so we have written this document to pro-vide some more specific guidance and ideas.Design ConsiderationsFirst of all, each team should spend a little time getting some background onthe PostScript language. We recommend you take a look at the PostScriptLanguage Tutorial and Cookbook (a.k.a. the “blue book”), which can beobtained by searching online or from http://inst.eecs.berkeley.edu/~cs161/sp08/Projects/psintro.pdf. Don’t worry about reading that doc-ument in detail! You should be fine just reading the first couple chapters andquickly skimming the rest, which should only take about 30 minutes or so.Also, the operator summary in the appendix may be a handy reference.The main question to be addressed in your design document is how youwill represent the syntax and (possibly to some extent) semantics of thePostScript language within your program. The most rudimentary approachwould be to include a list of PostScript keywords / built in operators (“add”,“def”, “dup”, “showpage”, etc.), then construct a test document by just con-catenating random sequences of these along with string and numeric literals.However, most such sequences will simply cause the PostScript interpreterto immediately exit with an error. For example, any sequence that beginswith “add” or any other operator that takes arguments will cause a stackunderflow as soon as the first token is read.1So in order to better test the1Of course, it would be good for your fuzzer to be able to generate highly invalid1interpreter, you will probably want to at least take into account the numberof arguments that each operator takes (pops off the operand stack) and thenumber of results it returns (pushes back on to the stack). Given that infor-mation, a random PostScript program could be constructed as an expressiontree, then output in postfix order to form a document which is valid at leastin terms of the operand stack. Since there are operators which take and re-turn a variable number of arguments (e.g., “copy”), you may not always beable to ensure this sort of validity, but that’s okay. You just want your fuzzerto be capable of eliciting a fairly wide range of behaviors from the interpreterrather than causing it to immediately exit with an error every time.Another thing to consider is whether your fuzzer will give any particularoperators or language constructs specific testing treatment. For example, the“get” operator indexes into arrays, so maybe you would want your fuzzer totest a range of negative or out of bounds values for the index. As anotherexample, you might want to test the interpreter on various sorts of quotedstring literals such as very long ones or ones with special characters. If youhave any specific types of tests such as these in mind, they could be eitherincorporated into your primary method for generating a random PostScriptprogram / document, or they could be separated out as distinct tests via theSPEC argument given to your fuzzer (see main project description).When considering these issues with respect the specially modified pstotext(1)program which will be provided for testing and grading, don’t pay too muchattention to how that program works. In particular, don’t worry about howthe actual pstotext program is implemented; you might as well assume weimplemented ours from scratch. Our only intention in selecting this programwas to pick a program that reads PostScript, so just assume it uses a com-plete PostScript interpreter / renderer internally rather than using some sortof shortcut that just extracts text.However you choose to design the high level approach to generating ran-dom PostScript documents, ideally your design will fit into a more generalframework for specifying data formats to your fuzzer (for example, the prob-abilistic context free grammars mentioned in the main project description).While not a requirement, a more general system will be easier to adapt toother programs, which may allow you to gain extra credit without muchadditional work.programs such as these, but if that is all it can do, its tests will not be very comprehensive.2Implementation ConsiderationsTo get you thinking about your design in greater detail, we’ve included be-low a list of implementation-level questions you should consider addressingin your Milestone 1 submission (in addition to the high level design issuesdiscussed so far). It’s not necessary to answer every one of these questionsin order to get full credit on your submission, but the more you address, thebetter the feedback we will be able to give you early in the project. Our goalis for the project to go smoothly and easily for each team, minimizing thework necessary to reach a satisfactory level of success!• What programming language(s) will you use to write yourfuzzer? Will there be any difficulties in compiling and running yourcode on ilinux1.eecs.berkeley.edu?• Are there any libraries or other external s ources of code youplan to use? If there is any library or existing source code that wouldreduce your work, we absolutely encourage you to use it. We’re nottrying to test your ability to write computer programs – the goal is tolearn about fuzz testing.• If you are planning on using a library, is it available on theilinux machines? If not, will you be about to bundle it up in thetarball you eventually submit so your program works? It’s fine toinclude a library or other external code in compiled form if that is theeasiest way to get it to work. Your code, however, should be includedas source.• How will you spawn the program being tested as a child pro-cess and check whether it has exited due to signal 11 or atimeout? In Linux, this is typically done through a combination ofthe fork(2), execve(2), and wait(2) (with WNOHANG in order to allowfor a timeout) system calls. In C/C++, they can be called directly;other languages often provide a higher level interface to this function-ality.• How will your fuzzer generate pseudorandom numbers? Just tokeep things straight, note that there are two separate “random” thingsthat your fuzzer will need to do. First, for each test run, it will need to3pick a new pseudorandom number generator (PRNG) seed. This neednot be reproducible, so you could just read however many
View Full Document
Unlocking...