Quiz 3 Flashcards
What makes two variables aliases?
They reference the same memory location
What has to decided for every pair of pointers at every program’s point?
Do the pointers point to the same memory location
What are the issues that may arise when analyzing pointers?
Do each pair of pointers point to the same memory location?
What pointers to report that do or may alias
Which pointers are ambiguous.
What will occur with this code?
Char *p;
*p = ‘A’;
It may or may not result in a segmentation fault because the pointer is not initialized
Give the alias set for the following code
int x,y;
int *p = &x;
int *q = &y;
int *r = p;
int *r = p;
int **s = &q;
{x, *p, *r}
{y, *q, **s}
{q, *s}
Give the Alias for this code.
int x = 10;
int y = 20;
int *p;
if (true)
p = &x;
else
p = &y;
{x, *p}
{y, *p}
{p}
What is a checker?
A program that is defined by a state diagram with state transitions and error states
How does the checker runs?
It assigns an initial state to each program variable
States at program point depends on state at previous point, program actions
Emits an error if a error state is reached
What are the three ways programs can be analyzed?
Static Analysis
Dynamic Analysis
Concolic Analysis
What is static analysis?
Inspecting code or run a automated method to find errors or gain confidence about their absence
What is dynamic analysis?
Running code with sample test input, possible under instrumented conditions, to see if there are likely problems
What is concolic analysis?
A hybrid program verification technique that performs symbolic execution, along a concrete execution path
What is symbolic execution?
A classical technique that treats program variables as symbolic variables
What are some examples of static analysis?
FindBugs, Fortify, Coverity, MS Tools
What is static analysis best used for?
Problem identification
Why is static analysis best used for problem identification?
It checks thoroughly and consistently
Can point to the root cause of the problem
Helps find error/bugs early in development
New information can be easily incorporated to recheck a given system
What is program verification?
Checks if a given input results in a correct given output
What are the advantage and disadvantage of static analysis?
Advantage: achieves completeness
Disadvantage: suffers soundenss
What is the most critical component of static analysis?
Constructing the model using data flows, control flows and pointer analysis
What is static analysis used for in security?
Finding bugs, verifying program correctness
Why isn’t dynamic analysis useful on its own?
It doesn’t give you a good enough explanation of what went wrong when the program fails
What is the leading cause of errors in C?
Memory corruption
What errors does AddressSanitizer detect?
Out-of-bounds array accesses
Use pointer after call to free()
Use stack variables after it is out of scope
Double frees or other invalid frees
Memory leaks
What are some issues with static analysis?
I can give alot of noise or unneeded information
It has both false positives and false negatives
Defects must be visible to the tool
What is the definition of soundness in regard to static analysis?
Sound for reporting correctness ie if theres a bug it reports it
What is the definition of completeness?
Complete for reporting correctness
What are the properties of static analysis?
Considering all possible inputs
Find bugs and vulnerabilities
Could prove the absence of bugs in some cases
What are the properties of dynamic analysis?
The sample test input must be chosen
Can find bug vulnerabilities but not prove their absence
Uses instrument code for testing
There is also blackbox testing for dynamic analysis: fuzzing and penetration testing
What is valgrind?
A general purpose dynamic analysis tool
What is valgrind used for?
Memory debugging, memory leak detection and profiling
How does valgrind function?
It runs programs on a virtual machine, this gives it a large amount of arbitrary transformations on the program
Why does valgrind have a very high overhead?
It shadows all program values: registers and memory, this also requires threads to be serialized
What are two use cases where valgrind would want to be used?
Complex memory bugs that are not detected by simpler tools
Complex profiling tasks
What does valgrind memcheck do?
Validates memory operations in a program
How does valgrind memcheck validate mem operations in a program?
Each allocation is freed once
Each access is to a currently allocated space
All reads are to locations already written
this results in around 10-20x overhead
What is the structure for instrumentation granularity?
Instruction
Basic Block
Trace
What is in the basic block for instrumentation granularity?
A sequence of instructions
Single entry, single exit
Termination point with one control flow instruction
What is in the trace for instrumentation granularity?
A sequence of executed basic block
What is Symbolic Execution?
Executing the program with symbolic valued inputs
What are some areas where symbolic execution is implemented?
KLEE, angr, Triton, Java PathFinder, etc
What is the symbolic engine?
What is the SMT solver?
A very complex mathematical solver
What are some issues with the symbolic engine?
Infinite execution tree
Exponentially many paths
What is concolic execution?
Combining concrete execution and symbolic execution?
What is the intention of concolic execution?
To visit deep into the program execution tree
What is Fuzzing?
Automated software testing
How does fuzzing work?
It generates invalid unexpected or random inputs to the program
What is dumb fuzzing?
Blindly mutating existing valid inputs
What is smart fuzzing?
It has two principles being generation based and being guided
What is generation based smart fuzzing?
Generating inputs according to protocol specification
What is guided fuzzing?
Collecting feedback to guide the next round of mutations
What is mutation based fuzing?
adding anomalies to existing valid inputs
What are some examples of things changed through mutations?
