Reimagined taint analysis system built upon deductive reasoning, counterintuitive philosophy, and human heuristics in real-world vulnerability research. We propose brand new dataflow analysis concepts ("State-recovery theory", "Parameter-first heuristic search", "Definition and Reference is All You Need"...), and tell a story how deductive reasoning - human's greatest cognition tool - played a role both in conceptualizing a bespoke dataflow system for Transformers, and enabling AIs in autonomous black-box taint analysis in binaries.

• Deduction over Computation
  • Deductive Reasoning (Human Fundamental (Cognitive Science / philosophy), hook
    • “logical process where a conclusion is drawn from a set of premises, where the conclusion is guaranteed to be true if the premises are true” (foreshadowing for both for development of Deductive Engine, and how it's based)
    • Exisiting sink doesn't stand mean it's a vulnerability. The essense of vulnerability lies in "exploitabiliy" and "reachability"
    • Traditional Taint Analysis:

      • a.k.a source-to-sink, taint propogation

        Calculating pre-(call-graphs and symbol), solving a "connect-the-dot problem". Build a graph first, given a source and a destination, query for a connectivity and a path in between.

      • Existing LLMs in taint analysis (e.g, LATTE), how the it's conceptually different.

  • No need for complex, holistic taint graph building, taint exploration based on linear deduction, parallel-able human though.
• Taint Reasoning (Epistemological system)

  • State-recovery theory (Deductive Dataflow analysis concept

    • Premise from Dissect the essence of dynamic pruning in taint analysis
    • "The exploitation of a taint function is not about exhaustive path enumeration, but rather a process of 'State Recovery"
      • "Where sinks are node with caller-chain states and parameter context, and the process of sink-to-source analysis is eventually a recovery of these hidden states, where one of these state is a source"
    • Explains why sink-to-source is a more sensible "context-relevant" (logical tasking, efficiency) task comparing to source-to-sink. Recovery instead of discover

  • Parameter-first heuristic search (Deductive Dataflow analysis concept)

    

    • Taint propagation methodology where where parameters acts as the fitness function of navigating for state recovery, proven works for sink analysis in research & development of tree-of-ast, state-rewind, lookahead
    • Context: Human in sink-to-source analysis
      • How five-nine of kernel, chromium vulnerability was discovered from thin-air
      • Predefined sink then definition, reference, definition, reference
      • Repeated navigation via deduction based on context
    • Dynamic pruning (original concept of Tree-of-AST) was implemented while LLM's ref/def with heuristically search via it

  • Definition and Reference is All You Need

    • Concept that a successful sink-to-source analysis can be conducted with and only with two fundamental symbolic navigational tools (definition & reference) with heuristically guidance (when to use which, when to stop).
    • Contrary to traditional taint-analysis

  • Stateful sink state-recovery (deducted from premises)

    • Methodology to recover sink's hidden states (grow Tainted Chain) of sink via deduction, heuristically supported symbolic navigation and "rewind" (stack jump-back).
    • "Stateful-sink chain" guarantees "sink-to-source" connectivity, we need restriction to source-to-sink connectivity, which would be complex if to consider both case in the first parameter heuristic search
    • Restriction Construction
      • Reversely traverse the generated taint chain, re-establishing source-to-sink analysis to makeup for the possible restrictions of branchings that we deliberately-neglected in with the heuristic stateful-graph recovery
        • exploitability-chain, chain-of-state where the source reaches to the sink, a prove of the reachability and exploitability of a vulnerability
• Deductive Engine in real-world (Wrap)
  • Black-box vulnerability-research in binaries