Read the summary and the most important questions on CS4106 Language-Based Software Security

• Lecture Notes 1

• Explain what normal forms, values and stuck terms are in Small-step operational semantics, and give the advantages of small-step operational semantics.

  
  
  
  There is a bit of terminology associated with reduction relations that will become useful:• Normal forms: Expressions that cannot be further reduced.
  • Values: “Good” normal forms, here numeric and Boolean literals.
  • Stuck terms: “Bad” normal forms, here ill-typed terms like 5 && true.
  To summarize, the advantages of small-step operational semantics are:
  • simple syntactic formalism
  • yields traces that allow us to observe every intermediate state of a program
  • works for non-terminating programs, yielding infinitely long traces 
  

• Lecture Notes 2

  This is a preview. There are 1 more flashcards available for chapter 24/11/2016
  Show more cards here

• We designed the Array language such that all array operations (except arlen) occur as statements, and we compiled the array language such that all array operations (except arlen) occur as instructions. What do you think was the reason for having these operations as statements/instructions?

  Expressions are not observable in the trace because we evaluate them in big step. Thus, if we want to reason about or affect array operations, we need to make them instructions in the compiled code.

• What is dynamic analysis? Give a pro and a con.

  A dynamic analysis checks a program property during the runtime of a program, that is, while the program is executing. That is, dynamic analysis prevents certain reduction steps to occur in a reduction trace.
  
  The main advantage of dynamic analysis is that it can access the runtime state of a program in order to identify violations of the checked property.
  
  Conversely, the main disadvantage of dynamic anlaysis is that it only detects violations at runtime (rather than at compile time).

• Array index out of bounds checking is a typical dynamic analysis. What languages do not check array access? What languages check array access statically at compile time?

  C does not check array access. I couldn’t find any mainstream language with compile-time bounds checking, but dependently-typed languages such as Coq and Agda perform compile-time bounds checking.

• What two techniques can be used to implement dynamic analysis?

  There are two common techniques for implementing a dynamic analysis: monitoring and instrumentation. For monitoring, we need to extend the language’s runtime to detect property violations. For instrumentation, we need to extend the language’s compiler to generate code that detects property violations when executed.

• Explain how runtime analysis through monitoring works. Give a pro and a con.

  The basic idea of monitoring is to extend the runtime to detect illegal state transitions. We can then abort the program execution or handle the detected violation in other ways (e.g., raising a catchable exception, or skipping the instruction that triggered the violation). 
  
  Advantages of monitoring:
  • Bounds check is guaranteed to be executed no matter what. • Works with any compiler.
  Disadvantages of monitoring:
  • Performance overhead for retrieving array size and bounds checking • Checks bounds even when the check is trivially satisfied.

• Lecture Notes 3

  This is a preview. There are 1 more flashcards available for chapter 01/12/2016
  Show more cards here

• What would happen if we did not use separate stack frames for each function call? 

  
  
  
  A recursive function would overwrite its own local variables accidentally. 

• What is taint analysis? What can it be used for? (2 examples)

  
  
  
  Taint analysis tracks the flow of sensitive data through a program and detects unprivileged access to such data. Taint analysis can be used for many purposes. For example, we can use taint analysis to prevent user-provided data to be submitted to an SQL engine without prior sanitation. Or we can use taint analysis to prevent non-privileged functions to access sensitive data. 

• What type of function calls do we need to identify as a preliminary for taint analysis?

  
  
  
  A preliminary for taint analysis is to identify three kinds of special function calls:
  

  • Sources of tainted information. As a convention, we will assume all functions whose name starts with “tainted” will yield tainted information.
    
  • Non-privileged information sinks that may not get hold of tainted data. As a convention, we will assume all functions whose name starts with “exposed” are non-privileged sinks.
    
  • Declassification renders sensitive information harmless and removes taint from it. As a convention, we will assume all functions whose name starts with “untaint” yield untainted results even if their arguments were tainted. 
    

• What approach can you use if you want to implement dynamic taint analysis, that is, track the flow of tainted information during a program’s runtime.

  
  
  
  he easiest approach is to maintain a set of all tainted memory locations somewhere on the heap. Alternatively, sometimes there is space available in the header of the data stored on the heap. For example, we could add a flag to the array header (if we wanted to treat all array elements uniformly). Languages with objects also often have a little spare space available in the object header.