Noninterference is a fundamental security property defined as: if two executions differ only in a secret input S, their observable outputs should be identical. Why is this a strong security guarantee?
Think about your answer, then reveal below.
Model answer: Noninterference ensures that secrets have no causal effect on observables. If an attacker can observe outputs, the outputs tell the attacker nothing about the secret (since changing the secret doesn't change observables). This rules out all information leakage through normal channels: the attacker cannot infer secrets from program behavior, output timing, memory consumption, or any observable effect. Noninterference is the gold standard of information flow security because it's composable (if A doesn't interfere with B and B doesn't interfere with C, then A doesn't interfere with C) and proof of noninterference guarantees secrecy.
Noninterference is stronger than typical security definitions because it considers the absence of information as a positive property. Many programs don't leak secrets through their outputs but leak through side channels (timing, power consumption). Noninterference captures all these by saying: any difference in observables that could allow an attacker to infer information about secrets is forbidden. Proving noninterference rigorously is hard, which is why static and dynamic analysis tools approximate it.
Question 2 Multiple Choice
Taint analysis tracks the flow of sensitive data (taints) through a program. If a password string P is tainted, and the program computes H = hash(P), is H tainted?
AYes, H is tainted because it depends on P
BNo, H is untainted because hash is a one-way function
CIt depends on the analysis. Conservative taint analysis marks H as tainted (information from P flows to H). However, if the analysis understands that hash is cryptographically secure, it might mark H as untainted because the hash doesn't leak information about P
DTaint analysis cannot handle hash functions
Taint analysis is a conservative approximation to noninterference: track data dependencies. If H depends on P (even transitively through hash), H is tainted. This is conservative (may mark data as tainted even if it's cryptographically safe) but effective at catching obvious leaks. Sophisticated analyses (like those in Android security or JavaScript sandboxing) understand cryptographic functions and skip tainting their outputs. The question highlights that taint analysis is a practical approximation to the theoretical ideal (noninterference) but with engineering pragmatism.
Question 3 Short Answer
Type-based information flow security assigns security labels to data (e.g., Secret, Public) and enforces that Secret data never reaches Public outputs. A program reads a password P (Secret) and checks if P == 'admin'. This produces a boolean result. Should the result be labeled Secret or Public?
Think about your answer, then reveal below.
Model answer: The result should be labeled Secret because it depends on the secret password. Even though the result is a boolean (not the password itself), it reveals information: if the result is true, the attacker learns the password is 'admin'. Type-based enforcement would raise an error if this boolean is used to determine a public output (e.g., 'access granted' message). The program would need to ensure the comparison result stays secret throughout its execution. This is a subtle but critical aspect of information flow typing: the type system prevents derived information from leaking, not just the original secret.
This is where information flow security gets subtle. A comparison result is 'derived secret' — it doesn't contain the original secret but reveals something about it. Type-based enforcement must propagate this: if a value depends on secrets, it is tainted/labeled secret, and cannot reach public outputs. The type system enforces this globally, preventing the most insidious bugs where secrets leak through derived values.
Question 4 Short Answer
Timing attacks exploit information leaks through execution time. A password checker loop terminates early if the password is wrong but runs longer for correct passwords (checking all characters). How can information flow analysis detect this vulnerability?
Think about your answer, then reveal below.
Model answer: The program's execution time depends on the secret password. Information flow analysis detects this by tracking data dependencies: the loop termination condition depends on the password (secret). If the execution time is observable (it is — an attacker can measure it), then the execution time correlates with the secret, violating noninterference. Information flow analysis would flag this as an error: the program's control flow (whether the loop continues) depends on secrets, and control flow determines timing, which is observable. To fix this, the program should always check all characters (constant-time comparison) so timing is independent of the password.
Timing attacks are a classic example of side-channel information leakage. The secret (password) is never explicitly leaked, but its effect on timing allows attackers to infer it. Information flow analysis catches this by recognizing that control flow depending on secrets leads to timing-dependent behavior. This is particularly important for cryptographic code, where constant-time operations are mandatory. Some languages (like Rust) provide constant-time cryptographic libraries; information flow analysis can verify that programs use them correctly.