# CS4239 Notes ## Table of content - [Notes](#notes) - [Table of content](#table-of-content) - [Purpose of Software Security](#purpose-of-software-security) - [Mitigation methods](#mitigation-methods) - [Ethics and Disclosure](#ethics-and-disclosure) - [Bug bounties](#bug-bounties) - [Possible causes of vulnerabilities.](#possible-causes-of-vulnerabilities) - [Generic Unix Process Layout](#generic-unix-process-layout) - [Computer Organization](#computer-organization) - [x86 Assembly Notes](#x86-assembly-notes) - [Common instructions](#common-instructions) - [Data Transfer](#data-transfer) - [Arithmetic](#arithmetic) - [Logical](#logical) - [Unconditional branches](#unconditional-branches) - [Miscellaneous](#miscellaneous) - [Conditional branches](#conditional-branches) - [Stacks and Vulnerabilities](#stacks-and-vulnerabilities) - [Calling conventions](#calling-conventions) - [Safe VS Unsafe languages](#safe-vs-unsafe-languages) - [Why are unsafe languages used](#why-are-unsafe-languages-used) - [Real life](#real-life) - [Memory Errors](#memory-errors) - [Buffer overflow](#buffer-overflow) - [OS Memory Error](#os-memory-error) - [Stack overflow](#stack-overflow) - [Buffer overflow exploit](#buffer-overflow-exploit) - [Heap Buffer Overflow](#heap-buffer-overflow) - [Code pointer corruption](#code-pointer-corruption) - [Null dereference](#null-dereference) - [Unsafe C Library APIs](#unsafe-c-library-apis) - [Format string vulnerability](#format-string-vulnerability) - [GCC Extensions](#gcc-extensions) - [Summary of common unsafe API](#summary-of-common-unsafe-api) - [Temporal Memory Errors](#temporal-memory-errors) - [Exploiting memory Vulnerability](#exploiting-memory-vulnerability) - [Dealing with memory errors](#dealing-with-memory-errors) - [Defense mechanism](#defense-mechanism) - [Enforce Policies](#enforce-policies) - [Compatibility](#compatibility) - [Testing vs Production](#testing-vs-production) - [Windows Fault Tolerant Heap](#windows-fault-tolerant-heap) - [Non-executable memories](#non-executable-memories) - [Stack protection / Detection mechanisms](#stack-protection--detection-mechanisms) - [Shadow Stack](#shadow-stack) - [Canaries](#canaries) - [Probabilistic Code execution prevention](#probabilistic-code-execution-prevention) - [Address Space Layout Randomization](#address-space-layout-randomization) - [Buffer overflow checking](#buffer-overflow-checking) - [Approach for checking buffer overflows](#approach-for-checking-buffer-overflows) - [Address Sanitizer](#address-sanitizer) - [Fat pointers (For better bounds checking)](#fat-pointers-for-better-bounds-checking) - [Defenses and their tradeoffs](#defenses-and-their-tradeoffs) - [Control Flow graphs](#control-flow-graphs) - [Call graph](#call-graph) - [Control flow Security](#control-flow-security) - [Control flow Integrity (CFI)](#control-flow-integrity-cfi) - [CFI Challenges](#cfi-challenges) - [Forward and Backward control flow](#forward-and-backward-control-flow) - [CFI Limitations](#cfi-limitations) - [Intel CET (Control Enforcement Tech)](#intel-cet-control-enforcement-tech) - [Windows CFI](#windows-cfi) - [LLVM CFI](#llvm-cfi) - [Evaluating CFI](#evaluating-cfi) - [Finding Bugs](#finding-bugs) - [Fuzzing features](#fuzzing-features) - [Fuzzing Assumptions](#fuzzing-assumptions) - [Oracles](#oracles) - [Functional Testing](#functional-testing) - [Systematic VS Random Testing](#systematic-vs-random-testing) - [Why functional testing](#why-functional-testing) - [Features of fuzzing](#features-of-fuzzing) - [Outputs of Fuzzing](#outputs-of-fuzzing) - [Black-Box fuzzing](#black-box-fuzzing) - [Mutational Fuzzing](#mutational-fuzzing) - [Generational fuzzing](#generational-fuzzing) - [Creating Structure in Fuzzers](#creating-structure-in-fuzzers) - [Grammar Approaches](#grammar-approaches) - [Fuzzing tools](#fuzzing-tools) - [Black box Fuzzing Blocks](#black-box-fuzzing-blocks) - [Comparing Grammar and Block](#comparing-grammar-and-block) - [SPIKE Fuzzer](#spike-fuzzer) - [When to stop fuzzing](#when-to-stop-fuzzing) - [Structural testing in practice](#structural-testing-in-practice) - [Statement Testing](#statement-testing) - [Node coverage](#node-coverage) - [Other coverage measures](#other-coverage-measures) - [Features](#features) - [Practical Fuzzing issues](#practical-fuzzing-issues) - [American Fuzzy Lop (AFL)](#american-fuzzy-lop-afl) - [Whitebox Fuzzing](#whitebox-fuzzing) - [Greybox Fuzzing](#greybox-fuzzing) - [Fuzzing challenges](#fuzzing-challenges) - [Concrete vs Symbolic](#concrete-vs-symbolic) - [Constraints](#constraints) - [White-box fuzzing](#white-box-fuzzing) - [Directed automated random testing](#directed-automated-random-testing) - [Challenges of symbolic execution](#challenges-of-symbolic-execution) - [KLEE](#klee) ## Purpose of Software Security - Understanding Security Problems - Gain better SE practice which promote writing of more secure software - Finding Security Vulnerabilities in code - Understand System Security and other Security related issues ## Mitigation methods - Patching / Fixing the Software - Disabling the application - Apply Defensive mechanism - Changing the environment or config to prevent the exploit ## Ethics and Disclosure - Responsible Disclosure - Disclose vulnerability to vendor ans takeholders and allow a time period to find mitigation or patch - How long to disclose? - Project 0: 90d - US CERT/CC: 45d - Reasons for Releasing the detail early - Defensive utility in sharing the details. - Opportunistic attacks using teh details between the CVE release and patch is reasonably unlikely. - Incentivises out of band patching and other mitigations developed / shared with urgency. - Reasons for not Releasing Early - Lack of evidence of active exploitation - Need more time to ensure maximum protection with minimal distruption - Impact was not very big ## Bug bounties - Financial rewards + Recognition from vendors / developers to report bugs - Allow developers to fix the bugs - Remedy 0-days ## Possible causes of vulnerabilities. 1. Programmers assume reasonable users and not attackers 2. Poor code quality 3. Reliance on undefined behaviour 4. Usage of unsafe languages (C) 5. Faulty Arithmetic 6. Legacy code 7. Bugs in libraries 8. Poor Testing 9. Misconfiguration 10. Interaction between softwares 11. Not dealing with exceptions 12. Faulty Security Policy 13. Over-privileged applications 14. Too much trust placed on input 15. Design errors / incorrect algorithms 16. Bugs in patches 17. Incorrect use of cryptography 18. Operating system vulnerabilities ## Generic Unix Process Layout 1. Kernel 2. Arguments & Environment Variables 3. Stack 4. Heap 5. Uninitialized BSS Segment 6. Initialized Data Segment 7. Text ## Computer Organization - Memory - Storage of instructions and data - Cache - Partial duplicate of memory for faster access - Usually split into instruction cache and data cache - Fetch unit - Load instruction from memory - Location indicated by a special register: Program counter - Functional Unit - Carry out the instruction execution - Dedicated to different instruction type - Registers - Internal storage for the fastest access speed - General Purpose Register (GPR) - Accessible by user program (IE: Visible to compiler) - Special Register - Program Counter (PC) - Stack Pointer (SP) ## x86 Assembly Notes 1. AT&T and `movl $1, %eax` (On AT&T) 2. `mov %eax, 1` (On Intel) 3. Data stored in little endian 4. Signed integers are stored in 2's complement 5. CPU Register (32-bit) 6. Memory accessed in C by dereferincing pointers 1. asm addressing modes 2. Specified as: Deplacement(base, index, scale) 1. means displacement + base + index \* scale 2. base, index: General purpose registers 3. displacement: 32-bit constant (default: 0) 4. scale: 1,2,4,8 (default: 0) 5. each part is optional 7. Operand size specified as suffix to the instruction mnemonic 1. b: byte 2. w: word (16-bits) 3. l: long (32-bits) 4. q: quad (64-bits) 5. optional if other operand is a register ## Common instructions ### Data Transfer 1. mov src, dst // dst = src 2. xchg dst1, dst2 // swap dst1 and dst2 3. push src // push src on top of stack 4. pop dst // pop stack and store in dst ### Arithmetic 1. add src, dst // dst += src 2. sub src, dst // dst -= src 3. inc dst // dst++ 4. dec dst // dst-- 5. neg dst // dst = -dst 6. cmp src, src2 // set CPU flags from expr (src2 - src1) ### Logical 1. and src, dst // dst &= src 2. or src, dst // dst |= src 3. xor src, dst // dst ^= src 4. not dst // dst = ~dst 5. test src1, src2 // set flags based on (src1 & src2) ### Unconditional branches 1. jmp addr // jump to addr 2. call addr // push return addr to stack, jmp addr 3. ret // pop addr, jmp addr ### Miscellaneous 1. lea src, dst // dst = &src 2. nop // do nothing ### Conditional branches 1. jcc addr // jumps to addr if condition cc holds 2. cmp %ebx, %eax; jb label; // Jump to label if %eax < %ebx 3. cmp %ebx, %eax; jnl label; // Jump to label if %eax >= %ebx 4. test %eax, %eax; jz label; // Jump to label if %eax = 0 5. cmp $0, %eax; jns label; // Jump to label if %eax >= 0 (signed) ## Stacks and Vulnerabilities 1. Stack Vulnerabilities allow exploits to violate integrity of stack layout 2. Function call stack 1. Stores variables for function 1. Arguments 2. Local Variable 3. Why stack storage 1. Handles recursion 2. Separate compilation 2. Stores administrative data (meta-data) 1. Return address 2. Stack frame pointer of caller 3. Exact details depends on compiler 1. CPU, OS 2. Win32 has many calling conventions 3. Stores Administrative data 1. Return address 2. Stack frame pointer of caller 4. Exact details depends on compiler, CPU, OS 1. EG: Win32 has many calling conventions 5. Stack is composed of frames 6. Function call 1. Logically pushed a new frame (composed of several items) on the stack 2. Includes passing arguments to function on the stack 3. Compiler may not do it with push instructions 7. Function 1. logically remove the current frame from stack 2. compiler may not do it with pop instructions 8. x86: stack grows to from high to low addresses, %esp register points to lowest valid address on stack ## Calling conventions 1. Function calling convention depends on the compiler + OS 2. Many different conventions are possible 3. x86 1. cdecl: caller cleans up stack -> GCC 2. Microsoft fastcall: 2 arguments in ECX+EDS, remainder on stack 3. thiscall: C++ this 4. Microsoft x64 calling convention 5. System V AMD64 ABI: Linux x86-64, Solaris, FreeBSD 4. Not going in depth into particular convention ## Safe VS Unsafe languages 1. Unsafe languages - Do not provide memory safety - Provide direct access to memory - Memory management is manual - Assumes programmer is correct but - Common source of bugs / vulnerabilities 2. Safe languages - Strongly typed: Java, C#, Scala, etc - Dynamically Typed: python, javascript, etc - Prevent memory errors - Memory management is automatic, eliminates programmer errors ## Why are unsafe languages used 1. Provide low level features 1. Can deal with hardware 2. Can deal with assembly language 3. Can manipulate memory 2. Can be more efficient 1. More optimizations are possible 2. Particularly C has many undefined behaviour which compiler canmakes its own decision to generate more efficient code 3. Legacy code / Compatibility 1. Dealing with large codebase 2. no desire/ability to rewrite code ## Real life 1. Much code is written C / C++ 1. Windows, Linux 2. Critical libraries, EG: OpenSSL 2. Safe languages also use unsafe languages at lower levels 3. Many attacks exploit bugs which can heppn in C / C++. ## Memory Errors 1. Focus on violations of memory safety 1. Causes + examples 2. Typical programming bugs in C 2. Why are memory errors important 1. Memory Errors usually are severe in impact. 2. Arbitrary memory modification/access, arbitrary code execution 3. Implementation defined behaviour. 1. Unspecified behaviour where each implementation documents how the choice is made. 2. Each implementation can choose. 3. The result of converting a pointer to an integer or vice versa. 4. The size of the result of subtracting two pointers to elements of the same array. 4. Undefined behaviour 1. Anything is allowed (It is not defined by the standard) 2. Value of & pointer to object outside its lifetime 3. Operand of \* has invalid value. 4. Value and accessing pointer outside an object 5. Array subscript out of range, even if object is apparently accessible 6. Invalid pointer given to signal handling function 7. String library function is used acess array beyond end of object 8. String library function called with invalid pointer 9. Compiler may choose the meaning 5. High level memory errors 1. Requires the full formalization of C standard 2. Undefined behaviour by C Standard 1. Allows for unknown / undefined behaviour by program 2. can interpret as undefined behaviour may be exploitable by attacker 3. Errors are those considered as unreasonable behaviour 4. Turned undefined into error 1. BOF -> undefined -> bug 2. Safe memory access -> Well defined by C standard 5. Access of undefined or invalid memory from OS Viewpoint 1. Dereferencing null pointer 6. Is undefined = error ok 1. Simple approach 2. Undefined = error 1. Not feasible in practice 2. Breaks real non-trivial code 7. Compatibility with code base 1. Not feasible to break existing code 2. Difficult to do so 1. We will look at some defenses later 8. Spatial memory errors 1. Bounds violation, accessing unitialized pointers 2. Deferencing NULL pointer, manufactured pointers from cast from arbitrary integers 9. Temporal memory errors 1. Access memory of object which has been deallocated 2. Dangling pointer, use after free 3. Invalid free, double free: May not be a temporal error 4. Memory leak 10. Other Errors: 1. Used on uninitialized memory ## Buffer overflow 1. A Spatial memory error 2. More correct to say spacial memory error but buffer overflow often used informally 3. Boundary condition 1. Address just after the last element of A is defined but should not be accessed. 4. Char in C is an integer type 5. Strings are array of char 6. Must be null terminated 1. No direct string length stored 2. null '\0' 1. Many vulnerabilities due to non-null termination of string 3. Byte integral value 0 ## OS Memory Error 1. Accessing undefined / protected memory leads to OS exception 1. Unix: Segmentation fault 1. Only catches some buffer overflow / memory access 2. Safe VS Unsafe languages 1. Safe languages: 1. Arrays bounds check is done during runtime 2. Has runtime check overhead 3. Will throw exception to indicate illegal access 2. Unsafe languages: 1. No array bounds checking 2. General problem is pointer access safety 2. Validity of pointer addresses 1. Distinguish between pointer value and dereferencing of pointer 2. ANSI C allows 1. Address of end of buffer + 1 is defined 1. Allows code like \*p++ 2. Also defined for start of buffer -1 2. Other addresses outside object are undefined 3. Some bounds checking solutions may not allow this 4. Might break standard compliant programs 3. Does not mean that they are exactly the same 1. Refers to pointer arithmetic and array indexing 2. Compiler turns array access into pointer usage ## Stack overflow 1. Local buffer (on the stack) overflow 2. Corrupts stack which has (possibly): 1. Data: Local variables, saved registeres 2. Control: Return address, frame pointer (saved %ebp) 3. Attack can violate 1. Control flow integrity 2. Data values integrity 4. Control Flow 1. Attacker can control return address with chosen input 1. New return address comes from data 2. A form of ROP 5. General stack corruption 1. Can corrupt return address for caller 2. Can corrupt multiple frames 3. Can corrupt data ## Buffer overflow exploit 1. Buffer data can contain new code to execute 1. Need to have address for control flow transfer 2. Can be guessed, shellcode can have nop instructions so can try many different addresses 2. Return to libc attack 1. No need to have new code, just return to existing libc code 2. Return address overwrite is function to call 3. Return-Oriented Programming attack 1. Generalize Return to libc 2. Return to any code fragment ending with ret-type instruction 3. Chain multiple fragments to execute code controlled from stack ## Heap Buffer Overflow 1. Buffer overflow outside stack 1. Sometimes refers to not just on the heap but elsewhere 2. Exploit is more tailored to program's code 3. Overflow names in structs ## Code pointer corruption 1. Hijack control flow when the function pointer is called. ## Null dereference 1. Usually causes OS Exception (Might not always be the case) 2. Usually expoint is on availability. ## Unsafe C Library APIs 1. Some C library functions are inherently unsafe 1. `gets()` 1. Gets bytes from standard input until '\n' or EOF 2. Amount of data written to buf is controlled by input. 3. No way to restrict to sizeof(buf) 4. Should not be used. 2. `fgets()` 1. Reads bytes from stream F into buffer s until n-1 or newline is read and transferred to s 2. No overflow but adds newline to `s[]` 3. `strcpy()` 1. Potentially unsafe 2. Copies string s2 to s1 including the null terminator 3. Possible Buffer overflow if strlen(s) >= len(buf) 4. Strlen can still go past non-null terminated string 4. `sizeof` 1. size of pointer and array is different 2. Some C library functions have to be used with care 1. `strcpy()` 3. Some safer versions 1. `strncpy(s1, s2, n)` but caveats 1. Does not add null terminator if `strlen(s2) >= n` ### Format string vulnerability 1. Many potential buffer overflows from format string in `printf()` and `scanf()` family of functions 2. `printf()` uses variable # arguments of C(varargs) 3. `sprintf(buf, "line %d %s", line, s);` 1. Intent to log some lines but `s[]` can overflow the buffer `buf[]` 2. Buffer overflow is similar to `gets()` 4. `printf("%s%s%s", p);` other arguments may be read from stack. 5. "%n" conversion 1. Dangerous feature: writes # chars written so far to value pointed bu argument 2. Can write int to arbitrary address in memory 3. C11 removes with `_s` version of function 6. Similar to `gets` problems with `scanf()` ## GCC Extensions 1. Extra error checks with gcc extensions ## Summary of common unsafe API 1. No check for size of destination output, no check for null pointers, output may not be null terminated 2. No check for null pointers, output may not be null terminated string 3. Requires buffers with null terminated strings 4. Format strings need to be written carefully (Some versions with no limit on buffer overflow) 5. Inherently unsafe ## Temporal Memory Errors 1. Access memory of object which has been deallocated 2. Dangling pointers / Use after free 3. Invalid free / double free: May not be a temporal error 4. But can cause problems for `free()` 5. Memory leak 1. Failure to free memory 6. Memory leak 1. Heap memory which is allocated but no longer accessible is not freed 2. Fix by adding free() add the right places 7. Failure to initialize heap 1. Wrong assumptions that heap will be zeroed 8. Failure to check if memory allocation succeeded 1. Code should check that malloc, calloc and realloc did not fail ## Exploiting memory Vulnerability 1. Unexpected code execution 2. Corruption of data 3. Revealing data 4. Crashing execution ## Dealing with memory errors 1. Prevention 1. Writing code without bugs (May not be feasible) 2. Using strongly typed language to prevent memory errors 3. Analyse program for memory safety 1. Testing techniques are usually incomplete 4. Perform checks during execution 1. Defence mechanisms used during execution 2. Detection 1. Usually exception if error detected 3. Containment 1. Use virtualization and Security policies to limit damage of attack 1. Sandboxing with SELinux, etc ## Defense mechanism 1. Prevent the error from occuring 1. Checking for buffer overflow in Java 2. Detect some attack (may have occured) after the attack 3. Make certain exploits infeasible or increase difficulty of mounting the attack. 4. Probabilistic Vs Deterministic 5. Dimensions: 1. Enforced Policy, Cost, Compatibility ## Enforce Policies 1. Strength of the policy and how effective is the enforcement 2. False positive & False Negative (Given as a %) 3. False Negatives 1. Failure to detect / Prevent attack 1. Want to minimize this 2. Probablistic approaches: False negative > 0 3. Deterministic Approaches: False negative >= 0 1. Can have > 0 as detection might be incomplete 4. False Positives 1. False Alarm -> Not an attack 1. Potential incompatibility introduced 2. How viable are false positives 2. May cause unnecessary crashes (Due to exception) 3. Can itself be a problem (DOS) 5. Trade-offs 1. Balance between false positive and false negative 6. Cost 1. Tradeoff between cost and accuracy 2. Performance overhead 1. Is slowdown acceptable 2. Usually low cost mechanism required for real-world usage 3. Note that running services in Cloud / VM already have overheads 3. Space overhead 1. Is memory overhead acceptable? 1. Time cost usually more important 2. Usually this is less of a problem but some techniques may need 2 - 3x memory 1. Trace based techniques may need unbounded memory or spill to disk / network ## Compatibility 1. May be the most important issue 1. If it does not work with existing systems, it will be hard to implement 2. Is Source code required? 1. Are annotations / modification to code / specs needed? 1. Annotations not practical in large codebases 3. Is it compatible with binaries 1. Source code not required? 2. Do we need to modify binaries? 4. Does it support modules 1. Support separate compilation / individual binary modules 5. More accuracy may decrease compatibility ## Testing vs Production - Are the defenses used only in testing? - EG: Find bugs and fix - Can survive with some false positive - High overheads are livable - Production defense - Can false positive be tolerated? - Overheads might need to be lower ## Windows Fault Tolerant Heap - Limited defence but may still have uses - Deployment is simple - Low cost - Not really addressing the security problem - Not really a security mechanism - It just reduce crashes - Can help with some vulnerabilities - Mostly cheap techniques - Strategies - Extra padding + Stamps with magic values - Mitigate small buffer overflows - Zero blocks - Reduce initialization bugs - Delay frees - Queue up blocks for later freeing (Similar to quarentine zone) - Dont free during shutdown - Does not free blocks if the program is going to terminate ## Non-executable memories 1. Code injection attacks 1. Write data 2. Execute data 2. Strategy -> Prevent injected code from executing 3. Make some portions of the memory not executable 1. Needs OS + Hardware support 1. Flags in page tables to control if page can be executed or not 2. Can be emulated without NX but costly 4. OS NX Support (Non-executable stack) 1. Windows Data Execution Prevention (DEP) 2. OpenBSD (W ^ X) 1. Forces pages to be executable or writable but not both 5. Does not prevent attacks that reuse existing code 1. Return to libc 2. ROP 6. Needs to be turned off when executable data is required 7. JIT code 1. JS Engines 2. JVM ## Stack protection / Detection mechanisms 1. Reordering variables on stack 2. Move buffers above other data variables 3. Reduces data corruption from BOF ## Shadow Stack - Don't use normal stack for return addresses or check integrity against shadow stack - Located in the hard to buffer overflow part of memory - Prevents control flow hijack fron return address - Some compatibility issues may arise from synchronizing shadow stack and normal stack - Might have non-trivial cost - EG - Intel Control Flow Enforcement Technology - Shadow stack protected by page table protections - Special mode: Change instruction semantics of CALL / RET instructions - Needs support from OS - Prevent control flow hijack from return address - Some compatibility issues may arise from synchronizing shadow and normal stack - Might have race conditions - Instrumented Call - Forwad phases of control flow - Modify function call instruction sequence - Intel CET - Changes RET semantics as seen above - Compare normal stack return address with shadow stack saved address - Abort/Exception if not equal - Shadow stack overheads (Approx 9 %) ## Canaries 1. Stackguard 1. Add canary values between value to be protected 2. Assumes Buffer overflow will overwrite canary or be stopped by canary value 1. This might not be true 3. Canary Values 1. NULL , CR, LF, EOF etc 2. NULL can prevent strcpy attack 3. Random canary values can be used to make it difficult for attacker to predict what values to overwrite 2. Checking code will need to be inserted before `ret` instruction. 1. Requires recompilation of source code 2. Requires compiler flags 1. `-fstack-protector` 2. `-fstack-protect-all` 3. Attacker route 1. Guess canary 2. Discover random canary through other information leak attacks ## Probabilistic Code execution prevention 1. Makes code execution less likely 1. Uses Randomness 1. May not guarentess attack prevention 2. May not be really random 2. Idea 1. Do not prevent code injection 2. Do not prevent control flow transfer 3. Make it harder to find the correct address for code injection / control flow transfer 3. Can be hard to get random values 4. Software rand() is pseudo random -> deterministic given the seed 5. Better randomness with hardware 1. x86 rdrand instruction from hardware entropy source 2. Environment entropy 6. Be careful with random source. ## Address Space Layout Randomization 1. Randomize the position of some stack, heap, globals and code 1. In practice only some things are randomized 1. IE: Starting position 2. Usually Constrained to randomize at page level 3. Changing code position on Linux requires code to be compiled as position independent (`gcc -fPIC`) 1. Code generated is changed and may need more instructions + registers 2. Protection 1. Does not prevent the vulnerability 2. Makes it difficult for attacker to succeed assuming that attacker now doesn't know how to exploit code address of data address 3. Usually most compatible + lowest overhead 4. Can be considered software diversity approach (Prevents all the software from looking the same) 3. Some Caveats 1. How much entropy is within the randomization 2. Probabilistic defence -> Try guessing attacks 3. Not all windows DLLs are compatible with ASLR 4. The attacker can attack something non-random instead 5. Information leak can reveal addresses or decrease the entropy (EG: Format String attack) ## Buffer overflow checking 1. Prevent buffer / pointer overflow by checking that all accesses are valid 2. Need to instrument pointer code 1. Only instrumented code is protected 3. Tools 1. Valgrind, ASAN 4. More protection that other methods for spatial memory errors ## Approach for checking buffer overflows 1. Check pointer arithmetic 1. Does the pointer exceed the bounds 1. Not that field access is pointer arithmetic as well 2. Check address of pointer access 1. Check variable with pointer 1. Store metadata with variables 2. Object based 1. Recover bounds from object 3. Boundary checks 3. Limitations 1. Only Some arrays access are protected. 2. Does not protect all memory accesses 4. Different kinds of bounds error 1. Object bounds 2. Sub-bounds (Structs) 3. Allocation bounds (Malloc) 5. Example defenses 1. ASAN 2. Compiler defences 3. LowFat 1. State of the Art ## Address Sanitizer 1. Available in LLVM `clang -fsanitize=address` 2. Uses boundary checks with redzones 3. Shadow memory 1. Compact map of main memory to indicate which addresses can be accessed or not 2. Every 8 bytes of memory has 9 states 4. Redzones 1. Add no-access redzones around object 2. Takes up actual virtual address space 3. Affects cache 4. Redzones may need to deal with alignment 5. Usage of redzones address is detected as a Buffer overflow 1. Usually this is by instrumenting code 2. Redzone tracked using shadow map 6. Add redzones for everything which is to be protected. 5. Detecting temporal erros 1. `malloc` / `alloc`/ `realloc` 1. Clear redzone if poisoned of object memory 2. `free` 1. Poison object memory 2. Delay reusing memory for new mallocs 3. Poison redzone detects use after free 1. Using any poisoned memory is detected as a use after free 2. Re-use after free is not detected as the area will no longer be poisoned 6. Other features 1. Requires correct mainenance of shadow map 2. Redzone checks are incomplete, it only detects overflow in redzones 3. Increased memory usage 1. Redzone Space 2. Shadow map 4. Can call uninstrumented code 1. But memory usage should not conflict with shadow map 5. Does not make use of bounds checking ## Fat pointers (For better bounds checking) 1. Replace machine pointers with fat pointers 1. Changes object layout 2. increase memory usage 3. Inteferes with binary compatibility 2. LowFat Pointers 1. Encodes meta-information within machine pointer 2. Size of machine pointer is unchanged 3. Requires large address space (EG: 64 bits) 4. Bounds checking for heap 1. Heap provides freedom in allocation of addresses 2. Current low fat 1. Check heap allocation founds 3. LowFat allocators 1. Creates low fat heap pointers 2. Special memory layour 1. Details can be changed 2. Split into different regions 3. Non-low fat pointers always suceed in bounds check 4. Passing non low-fat pointers will not result in errors 5. Many other optimizations 1. Avoid division with fixed point arithmetic 2. Power of 2 sizes 6. 4. Faster than ASAN 5. Features 1. Low-Medium time overhead for heap buffer overflow 2. Low space overhead 3. Highly compatible 4. Can protect stack and head ## Defenses and their tradeoffs | Defence | Overhead | Effectiveness | Compatibility | | --------------------- | ------------- | ------------- | --------------------------- | | Non-executable Data | 0 | Low | High except JIT compilation | | Stackguard (Canaries) | Very Low | Low | High for source code | | ASLR | Low | Low-Medium | High | | CFI | Medium | Medium-High | Medium | | Buffer overflow check | Medium - High | High | High | ## Control Flow graphs 1. A direct graph 2. Nodes are basic blocks 1. Sequential operations and last one can be control flow transfer 3. Edges are control flow transfer from one block to another 4. Nodes can have multiple incoming and outgoing edges 5. Representes control flow of program 1. A model of how control flow works in a program at source code or binary level 6. Used on compilers, static analysis, etc 7. Might be dynamic and nto static 1. JIT compilation ## Call graph 1. Nodes in CFG as functions 2. Graphs that shows which function calls which functions ## Control flow Security 1. CFG expresses potential code paths and execution in program 2. Fixed by program code 1. CFG is static if program does not change 3. Programmer expects control flow to follow CFG 1. Attack changes envuronment of executing process 2. Original program may not hold 1. EG: ROP results in invalid CFG 3. Attack can change control flow from what program / CFG is supposed to do ## Control flow Integrity (CFI) 1. Attackers might want to change the control flow 1. EG For RCE 2. Usually memory error is the culprit 3. Memory defence -> Prevent the cause 4. Control Flow integrity -> Prevent the attack 5. Why 1. Memory defenses are costly 2. Can have fwer % overhead 1. May have weaker guarentees as a result 2. Tradeoff protection vs overhead 3. Many kinds of CFI with different tradeoffs 6. Idea 1. Limit the control flow transfers to what the program allows 2. Only allow control flow within the static control flow graph of the program 3. CFG Violation is when control flow does not follow the static CFG 7. False positive 1. Depends on accuracy of the CFG ## CFI Challenges - Hard to determine CFG accurately if there is dynamic behaviour - EG: Function pointers, virtual C++ Functions - Computing accurate CFG is undecidable - Over approximation usually used. (Allows for False Negative) - Errors in CFG can also cause false positive - Dynamic jumps from function pointers -> Need static analysis of possible addresses or approximate to all functions - What about exception handling / JIT - Pure static approach is insufficient ## Forward and Backward control flow 1. Forward branching (Jump or Call instruction) 1. Also called forward edge in CFG 2. Jump / Call target is indirect address 1. Why? -> Fixed target cannot be changed by attacker 3. Is Branch target possible? 1. Not possible -> CFI Violation / Error 2. Possible != correct 2. Backward branching (Ret instruction) 1. Also called backward edge in CFG 2. Is return target continuation of original call? 3. Can be checked with shadow stack defences 1. Note: StackProtector is not a backward edge defense 3. There are also fine grain / coarse grained CFI ## CFI Limitations 1. Only deals with control flow 2. Limits on control flow transfer needs to be approximation of true execution (Usually) 1. Jump / Call / Return impossible at runtime without attack 2. Under-approximation can cause errors / compatibility problems 3. Over-approximation may allow some attacks on CFI defense ## Intel CET (Control Enforcement Tech) 1. New instructions (Tiger Lake mobule CPUs) 1. `ENDBRANCH` instruction 2. Equivalent to `NOP` in processes without CET 2. A forward edge CFI 1. Target of indirect branch 1. Indirect Call / Jmp instruction 2. Next instruction executed must be `ENDBRANCH` otherwise exception is raised 3. Only in CET Mode 4. After `ENDBRANCH` execution is back to normal 2. Coarse Gained CFI 1. Single label for all the functions 2. Does not distinct between function 3. Instruction is also the Label 3. Backward Edge CFI 1. Protection with Shadow Stack 2. Protected by Page table protections 3. CET Mode: Changes instruction semantics of `CALL/RET` instructions 4. New Shadow Stack Pointer (SSP) register 5. `RET` instruction compares return from SP and SSP 1. Exception if no match 6. Needs OS + Compiler support ## Windows CFI 1. CFI on Windows -> Windows CFG 2. Partial CFI: Control Flow guard in Windows 8, 8.1, 10. 3. Does not protect return control flow 4. Coarse grained CFI Protection 5. New CFI 1. Windows Extreme Flow Guard (xFG) 2. More fine grained than CFG 1. Check type signature ## LLVM CFI 1. Sanitization options 1. Eg: [here](https://clang.llvm.org/docs/ControlFlowIntegrity.html) ## Evaluating CFI 1. Low overhead schemes use coarse grained CFI (False Negative might be more) 2. Forward edge only CFI more common 1. Overhead of shadow stack may not be small 2. Shadow stack can have `edge cases` attacks 1. EG TOCTOU 3. Still can have attacks 4. Data Oriented Programming (ROP for CFG) ## Finding Bugs 1. Verification / Model checking 1. Formal Proofs, clear guarentees 1. Systematic / Exhaustive 2. Very hard (Undecidable in worst case), not scalable 3. Automation is limited 2. Static Analysis 1. Verify certain properties (EG: Memory safety) 2. Automation, clear guarentees 3. False positives, less scalable 3. Reverse Engineering / Source Code auditing 1. Good: Exploit human ingenuity 2. Bad: Mostly / Partly manual, not scalable 2. Testing 1. Penetration Testing 2. Software Testing 3. Fuzzing 1. Can be mostly automated 2. No guarentees, expensive runtimes ## Fuzzing features 1. No definition 2. Elements of fuzzing 1. Input / interface testing 2. Random element to test generation 3. Find bugs using crashes / errors / abnormal behaviour 4. Many frameworks + automation 3. Limitations of testing / Fuzzing 1. May find some bugs 2. No guarentees 3. Cannot show absence of bugs 4. However, many vulnerabilities are still found using fuzzing ## Fuzzing Assumptions 1. Input (Test case) encodes the bug 2. Buggy inputs crashes the program 3. Minimal or no Source code 4. Strategies + Algorithm to exercise the assumptions 1. Can be automated ## Oracles 1. Strong Oracles (For testing) 1. Ways of determining that execution / output is correct 2. Weak Oracle 1. Weaker proxy of String oracles 2. Does not check for correctness (Of output / behavior) 3. Weaker property (May or may not indicate "correctness") 1. Assertion failure 2. Memory error -> Segfault 3. Timeout 4. Crash ## Functional Testing 1. Derive test cases from program specifications 1. Functional refers to the source of information used in test case design, not what is tested 1. EG: Unit testing 2. Also known as black box testing / Specification-based testing 3. Only knows the intended program behaviour 1. Either formal or informal ## Systematic VS Random Testing 1. Random (Uniform) 1. Pick possible inputs (Uniformly) 2. Avoids Designer Bias 3. Treats all inputs as equally valuable 2. Systematic (Non-uniform) 1. Try to select inputs that are more valuable 2. Cannot test all inputs 3. Usually by choosing representatives of classes that are apt to fail often or not supposed to fail 1. Based on past experiences 4. Can be in the form of partitions 3. Functional testing is systematic testing 4. Fuzzing is close to random black-box testing 5. Possible to combine both 1. Can be less expensive and effective strategy in practice ## Why functional testing 1. Timely 1. Often useful in refining specifications and assessing testability before code is written 2. Effective 1. Find some classes of fault that can elude other approaches 3. Widely Applicable 1. To any description of program behaviour serving as a spec 2. At any level of granularity from module to system testing 4. Economical 1. Typically less expensive to design and execute than structural test cases 5. Program code is not necessary 1. Only description of intended behaviour is needed 2. Even incomplete and informal specifications can be used 1. Although precise, complete specifications lead to better test suites 6. Early functional test design has side benefits 1. Reveals ambiguities and inconsistencies in spec 2. Useful for assessing testability 3. Useful explanation of specification 1. Or in the extreme case, test cases are the spec ## Features of fuzzing 1. Automated test generation 1. Favours slightly anomalous or malformed or illegal inputs 2. Apart from this issue, try to keep test generation random 2. Automated test execution 1. Needed -> No programmer involvement 3. Automated and weak notion of test oracle 4. No notion of expected output to see if a test is passing 5. No test case needed but can have seed inputs 6. Simply see if the application hangs / crashes / in a strange state 7. Crash -> Usually memory error / Exception 1. Memory Defenses help find more cases 1. ASAN / LowFat 8. Detailed record keeping 1. For crashing tests, one may find many crashing tests by fuzzing 9. Independent of any programming language / OS etc 1. No analysis, only execution 2. Some execution book keeping may be needed 1. Coverage guided fuzzing. ## Outputs of Fuzzing 1. Lots of crashing test inputs 1. Not directly useful 2. Many tests might be a manifestation of the same vulnerability 2. Cluster Crashing tests 1. Ideal 1. Semantic analysis of test to find a "reason" 2. Capture reason as logical formula 1. EG: Whitebox fuzzing 3. Store a bucket of tests against each logical formula 2. Actual (Usually) 1. Cluster tests based on point of failure 2. Failure location / function where failure occurs / path in CFG 3. Cluster tests based on call-stack similarity 1. Windows Error reporting system 3. Developers might completely ignore fuzzing output otherwise ## Black-Box fuzzing 1. Randomly Permute String as input, try to crash (Unix) program 2. Simple and surprisingly highly effective 3. Problem with code coverage and checksums ## Mutational Fuzzing 1. Inputs 1. Program P 2. Seed 0x1 3. Mutation ration 0 < m < 1 2. Obtain input by mutation operations 1. Randomly flipping bits 3. Run x1 and check if P crashes or terminates properly 4. Document the outcome and generate next input 5. End of fuzz campaign 1. When time bound is reached, or N inputs are explored for some N 2. Can check that mutation does not run the same input twice 6. Many program take in structured inputs 1. Completely random input will most likely crash the application without much useful information 2. Instead we can take a legal input and mutate it 7. Principle of mutation fuzzing 1. Take well-formed input which does not crash 2. Minimally modify or mutate to generate a slightly abnormal input 3. Check if input crashes 8. Salient features 1. Does not depend on program at all 2. Does not even depend on input structure 3. Yet can leverage complex input structure by starting with a well formed seed and minimally modifying it ## Generational fuzzing 1. Mutations can be random 1. Small probability of re-producing a specific crash in a specific byte deep down in the input file 2. Huge number of mutations to try out 2. Mutations can produce ill-formed inputs 1. A mutated input file with incorrect check-sum 3. To avoid these, generational fuzzing can be used 1. However, it requires the specification. ## Creating Structure in Fuzzers 1. Split into different parts 1. Structured part -> May be part of protocol 2. Fuzzing part -> Can be mutated by a fuzzer ## Grammar Approaches 1. Selectively mutate the input based on the grammar to produce almost correct input 1. Ensure checksums are valid 2. Mutating subset of input affecting more interesting paths 3. Higher coverage of the program can be acheieved by selectively fuzzing the different portions of the input ## Fuzzing tools 1. Build one for protocols 2. Spike Fuzzer 3. Peach Fuzzer 1. Can be augmented using grammars or input domain specification 4. Given a specification, there exists possiblity to prioritize tests 5. Starts to move towards white-box apprach from black-box approach ## Black box Fuzzing Blocks 1. Aitel proposed using block-based input generation in SPIKE framework 2. Input made up of blocks 3. Each blocks have rules on generation written in API form 4. Simpler than grammar based fuzzing ## Comparing Grammar and Block 1. Grammar 1. Provides understanding of behaviour and syntax 2. Guides fuzzing based on this understanding 2. Block 1. Identifies a rough structure of the input 2. Aimed at re-using previously known correct structures to generate new inputs ## SPIKE Fuzzer 1. Is a block based fuzzer 2. Make it easy to reproduce a complex binary protocol 3. Develop a base knowledge within SPIKE about different kinds of bug-classes affecting similar protocols 4. Test old vulnerabilities on new programs 5. Make it easy to manually mess with protocols 6. Data structure 1. First in First Out queue 2. Automatically fill in "length fields" 3. String variables are fuzzed by Spike 7. API Calls can be made using a simple interpreter script ## When to stop fuzzing 1. When time budget is exhausted 2. When sure that most of the behaviour of the program is covered 1. Statement coverage 2. Branch coverage 3. Path coverage 3. Measuring the adequacy of black-box fuzzing requires us to look inside the code 1. However, it can be machine code (Binary) 2. Can measure by instrucmenting code (Binary / Compiler rewriting) ## Structural testing in practice 1. Amount of code covered in execution by a single test suite 1. Create function test suite 1. Measure structural coverage to idetify and see what is missing 1. Interpret unexecuted elements 1. Attractive because it can be automated. ## Statement Testing 1. Each statement must be executed at least once 2. Statement coverage = #executed stmt / #total stmts 3. Rationale 1. A fault in a statement can only be revealed by executing the faulty statement 2. Assumes no state dependence (Statements are independent) 1. This may not be true ## Node coverage 1. Cover all nodes in a control flow graph 2. 100% Node coverage -> 100% Statement coverage ## Other coverage measures 1. Node coverage 1. Not the same as edge coverage, edge includes every possible way to enter the node 2. Edge coverage 1. #executed branchs / #total branches 3. Path coverage 1. Strictest 2. Decision and condition adequacy criteria consider individual program decisions 3. Each path must be executed at least once 4. #Executed paths / #Total Paths 5. The number of paths is possibly unbounded 6. For feasibility 1. Infinite paths partitioned into finite number of classes 2. Number of traversal of loops is limited 3. Length of paths limited 4. Dependencies limited ## Features - Coverage does not depend on the number of tests, - However, smaller tests make failure diagnosis easier - Measured from execution - Changes in coverage requires changes in input - Full coverage is usually unattainable ## Practical Fuzzing issues 1. Blackbox random testing may not generate useful test cases 1. Without timeout limits 2. Can be combined with the following 1. Runtime knowledge 2. Learnt test cases ## American Fuzzy Lop (AFL) 1. Coverage-based Greybox fuzzing 1. Instrumentation of CFG Edges 2. Very successful in finding vulnerabilities 3. Input testing fuzzing 4. Automated 1. Only uses seed inputs 2. Can even be empty inputs 5. Open source 6. Counts CFG Edges executed 7. Coverage array is 64kb shared memory region 8. Adds low overhead 9. IsInteresting strategy 1. If it creates new coverage tuples, it will favour it 10. Deterministic Strategies 1. Sequential bit flips 11. Non-deterministic strategies 1. Stack operations 2. Splice test case 12. Architecture 1. Load / mutate test case 2. Execute target app 1. Fork server 2. Target process runs main with test case 3. Driver waits for termination / exit 4. Target code has AFL instrumentation 5. Fork server uses shared memory as coverage bitmap 3. Driver collects bitmap to decide if input is interesting 13. Scales to N cores in parallel 14. AFL termination 1. Timeout / Normal Exit 1. No errors found 2. Error Found 1. Successful crashing input = Found buggy test cases 2. Exception / Security instrumentation = Crash 3. Segmentation fault / Bus error / Sigill 4. ASAN memory error -> Combine AFL + ASAN 5. Malloc allocator which can exercise more errors 15. Enhancements 1. AFLFast 1. Better use of feedback 2. More effective search Strategy 2. Driller 1. Adds intelligent input generation to AFL 2. Symbolic execution 3. WinAFL 1. Windows support 2. Dynamic instrumentation at runtime 4. Many more 1. AFL continually enhanced ## Whitebox Fuzzing 1. Looking inside the box 2. Program behaviour 3. Program analysis 4. Execution monitoring 5. More information is included, usually Source code ## Greybox Fuzzing 1. Less information thatn whitebox 2. Between Whitebox and Blackbox ## Fuzzing challenges 1. How to find a test to hit certain code 1. Check specific assert in code 2. Can we have in principle guarentee 1. Achieve full code coverage 2. Doesn't mean can guarentee full coverage 3. Symbolic execution approaches 1. Systematic approach 2. Full guarentees may not be possible 1. Some tasks are theoretically very hard 3. How to generate the right input 1. Black box fuzz generation like `finding needle in haystack` 2. Fuzzer may never find the desired input test case ## Concrete vs Symbolic 1. Concrete input 1. Given actual test case what is the behaviour. 2. Conventional execution 2. Symbolic input 1. Do not know the test case 2. What test cases reach line M 3. No concrete value specified 4. Can be potential set of values and may not be known ## Constraints 1. Path conditions are "contraints" 2. High level view 1. Yes -> there is a solution 2. No -> No Solutions 3. Hard to solve inequalities 4. String contraints 1. Let s be string, R be a regular expression 2. Solving this might be undecidable 5. Non-linear arithmetic 1. Transcendental functions are undecidable in general 2. Multivariate polynomials over the integers are undecidable 6. Constraint solving varies from 1. Easy to difficult to impossible 2. Some cases still can be solved (Not all are hard) 7. Many inputs can take on the same path 1. Depends on exact code 2. Inputs taking ## White-box fuzzing 1. Directed automated random testing 2. Symbolic path exploration engine 3. Automatic extraction of interface 1. Automatic determine inputs to the program 2. Variables which depends on environment 3. Function calls 1. Return value depends on the environment 2. External function call 4. Generate Random test driver 1. Automatically simulate random environment of the extracted interface 1. Can be most general environment 2. Compile the program along with the test driver to create a closed executable 3. Run executable to see if assertion is violated 5. Fuzzing driver limitations 1. Hard to hit assertion violated with random values of x and y ## Directed automated random testing - White box approach - Based on source code - Mix concrete execution + Symbolic execution = Concolic execution - Keeps track of symbolic execution state and constraints - Collect symbolic constraints at branch points - Call constraint solver on path condition to generate new test inputs - Use test inputs for next execution - Negation of constraints may not be trivial - EG: String constraints - In practice many tools rely on complex constraint solvers - Lightweight - Real tool that works on C Programs but has limitations ## Challenges of symbolic execution 1. Constraint solver may not be complete 1. Not all cases can be handled 2. Negation of constraint may be problematic 3. Solving path constraints may be intractable / undecidable ## KLEE 1. Can mix concrete + symbolic inputs 2. concolic / dart uses concrete 3. Compiles C code to LLVM UR 4. Uses STP constraint solver 5. Used to check GNU Coreutils and covered 90% of the lines 1. More than 15 years of manual test suite