In this course, you will use a variety of tools implemented in different programming languages to generate useful facts about a program’s behavior and analyze them. You will learn about the tools and their theoretical underpinnings in this course, however it is assumed that you are already familiar with basic concepts in computer science and mathematics, as well as the use of various tools/commands in a UNIX-like environment.
This assessment is designed to help you determine specific skills and concepts you should learn or refamiliarize yourself with prior to starting this course. You do not need to master each and every one of these skills - but you should have command of the majority of them. While it will be possible to pick up some of these skills along the way, it will prove difficult to cover them all (especially true in shortened summer semesters).
The instructors and teaching assistants have only a limited capability to assist students with learning these tasks, and they will not be explicitly covered in video lessons.
In this course, assignments are completed on a Virtual Machine (VM) that is provided by the teaching staff. This VM is a common operating platform that is also used for grading, which ensures that the code you create on your VM will behave the same way when it is graded. You should be comfortable with using VirtualBox, including importing a VM from a .ova file, adjusting VM settings (network, memory allocation, etc,). If you are unfamiliar with virtualization, you can find more information here.
All assignments in this class assume a UNIX-like environment. You should be comfortable browsing folders and executing basic commands from a UNIX command prompt.
Sample task: Using just a command prompt in a UNIX-like environment (such as Linux or macOS), create a new folder, create a text file inside that folder, and change the file permissions to allow execution of that file (such as would be needed if the file contained a shell script). Finally, create a ZIP archive of your folder and extract it to a different location to verify that it was correctly created.
For some assignments, you’ll need to write a shell script that can execute a command. You may use any common UNIX shell scripting language such as bash, csh, or even python.
Write a script that can be executed with the command
./myscript.sh input.txt output.txt that takes an
input text file and produces a version of the file that is sorted using the UNIX
sort program. Your program
should produce an
output.txt that contains just Error if the input causes sort to crash.
You will be performing analysis on common data structures such as trees, heaps, queues, and stacks. You should be able to write code in Java and C++ that can use common data structures.
Sample task: Using a high level language such as Java or C++, write a class that builds a balanced binary tree out of an unsorted array of integer values. Then write a search function to determine if a specific value exists in the tree. Your search function should use an algorithm such as a BFS (Breadth First Search) or DFS (Depth First Search) on the tree values and return false if the desired value does not exist in the tree.
Sample input array of values: [26, 28, 76, 32, 4, 87, 42, 9, 12]
Some tools we explore in this class automatically generate test cases that will find bugs in a provided application. You should be able to use a compile error or stack trace to figure out why a source file doesn’t compile. Additionally, you should be able to find and fix issues such as null pointer exceptions or invalid cast errors in a code file. As many applications we will be analyzing are relatively simple, we recommend having a high level of comfort debugging simple issues without the help of an IDE.
Sample task: Run the following Java program. Make sure that all code in the main method executes to produce correct results.
Many software analysis tools require more knowledge of the tool than will be provided in assignment instructions to effectively use the tool. You should be comfortable reading the documentation that is provided with tools and utilities. In particular, one great resource available for many tools are man pages. Most UNIX tools provide a man page that gives basic usage instructions and how to modify the command to accomplish different tasks.
uniq UNIX tool to take the following text (copy it into a text file) and remove duplicate lines.
Modify your command to do the following things:
mancommand to figure out the capabilities of
Some of the analysis and testing techniques exploit the power of randomness. While a thorough understanding of probability and statistics is not necessary for success in this course, you should be familiar with the concepts of the Random Distribution and Random Sampling. You should be able to apply these concepts to randomized algorithms and reason about the likelihood of a particular program behavior.
Sample task: Assume you are writing a program to randomly award a prize to contestants. Contestants enter a 32-bit unsigned integer at random. If the number entered is between 50 and 65 and divisible by 5, the contestant wins.
The primary focus of this course is Software Analysis. Software can be analyzed at various stages in its life cycle including in its source code written by the programmer, an intermediate representation generated by a compiler or language toolchain, and in the program’s binary representation.
While extensive knowledge of compilers, toolchains, and runtimes is not necessary for this course, in general you should have a working knowledge of what happens to your code when you “build” it.
Sample task: You should be able to answer the following questions regarding code build processes: