commit 104efd26339a2471d68d9820cf7417a2ff1d9b0e
parent 9113a280893f9493a01519d7af1510dbc4a36f62
Author: Jared Tobin <jared@jtobin.io>
Date: Wed, 21 Oct 2026 11:03:16 +0400
merge impl/gaps: the gaps a review found, closed
- checks: a probe harness (etc/probe/harness.c) under both
instruments, and built for aarch64 differentially on an x86_64
host, each report held to exactly what the harness does
(checks.<system>.probe, on Linux).
- plugin: an instruction named by its address in its object, from
the file's program headers, not its file offset; a GHC harness
linked at a fixed address had every origin unnamed.
- plugin: a guest that starts a second thread is stopped and its
dump refused, rather than recorded by threads racing on unlocked
state.
- record: the run's arguments, environment size, and exit status
appended to its dump; diff refuses runs of another program or with
arguments or an environment of another size than the first run's,
and a control that does not repeat the first run's arguments.
diff-v3 lists each run with its arguments and status.
- record: QEMU chosen by the harness's ELF machine, so an aarch64
harness traces on an x86_64 builder.
- diff: a return is downstream, never an origin (Penumbra's `retq`
origins, four or five a root, gone and nothing else).
- diff and memcheck: an integer division on other operands, or on an
undefined one, is an `operand` origin or site (the plugin reads
the operands; nix/memcheck-operand.patch adds UninitOperand), and
memcheck keeps the instruction pointer exact at every instruction
so a register division is named where it divides.
- trace: taint over every run, merged (run --dir, read RUN...,
trace-v2, traceOf's runs), each site with the runs that reached it.
- symbol: LLVM's addr2line, which names inlined frames by their own
functions and code no symbol covers by none; legacy Rust names
unescaped.
- diff: each origin with the calls that reached it, from a shadow
call stack in the plugin, as `stacks` shaped as a taint report's.
- README and CHANGELOG say what changed, and the caveats left: an
address a secret branch moved, other variable-time instructions,
GHC's calls and returns by jumping.
Built and tested on pollux: the probe check, the unit suite, and the
Penumbra, poly1305, and secp256k1 spikes.
Diffstat:
18 files changed, 1971 insertions(+), 340 deletions(-)
diff --git a/CHANGELOG b/CHANGELOG
@@ -4,30 +4,48 @@
* Initial version, with two instruments over a harness that marks
its secret (`vestigia.h`, defined by `vestigia.c`, which serves
a foreign function interface too and records where the loader
- put each object):
- * `vestigia run`: the harness under memcheck with the secret's
- bytes undefined, reporting each branch and address computed
- from them (vestigia/trace-v1); `vestigia read` reports from
- memcheck's XML.
- * `vestigia record` and `vestigia diff`: the harness under QEMU
- with vestigia's plugin, its leakage trace summarised per
- instruction, and where runs differing only in the secret
- diverge (vestigia/diff-v2: each origin with the runs alike
- there and the runs that never reached it, a branch taking its
- outcomes in another order an origin too, and what ran
- downstream listed per object), set against controls repeating a
- secret, with what every run executed in each object, and runs
- designed to reach particular paths compared for control and
- coverage alone (`--designed`); runs are recorded with
- randomisation off (or not at all) and the guest's entropy,
- its getrandom included, seeded, and QEMU's own allocations kept
- off the guest's mappings, which under load can otherwise take
- the room of a guest library or heap; `diff` refuses runs that
- loaded an object at different addresses. A taint run that
- marked no secret is refused.
- * `traceOf` and `diffOf` run either as a derivation;
- `nix/lib.nix` holds them for any package set, with the version
- the command reports.
+ put each object). A taint run that marked no secret is refused.
+ * `vestigia run`: the harness under memcheck with the secret's
+ bytes undefined, reporting each branch, address, and integer
+ division operand computed from them (the last through a memcheck
+ patch, `nix/memcheck-operand.patch`), each at its own
+ instruction. `--dir` keeps a run, and `vestigia read` reports on
+ several kept runs, or memcheck XML made elsewhere, as one
+ (vestigia/trace-v2: each run with its command, exit, and
+ objects; each site with the runs that reached it).
+ * `vestigia record` and `vestigia diff`: the harness under QEMU
+ with vestigia's plugin, its leakage trace summarised per
+ instruction, and where runs differing only in the secret diverge
+ (vestigia/diff-v3):
+ * each run with how it was made, its arguments and exit status;
+ * the origins: a branch taking its outcomes in another proportion
+ or order, an instruction touching other addresses, and an
+ integer division on other operands, a return never one; each
+ with the runs alike there, the runs that never reached it, and
+ the calls that reached it;
+ * what ran downstream, and what every run executed, per object;
+ * controls repeating a secret, what differs in them set apart as
+ unsteady, and runs designed to reach particular paths, compared
+ for control and coverage alone (`--designed`).
+ * `record` runs an x86_64 or aarch64 harness on either host, with
+ randomisation off (or not at all), the guest's entropy, its
+ getrandom included, seeded, and QEMU's own allocations kept off
+ the guest's mappings, which under load can otherwise take the
+ room of a guest library or heap. The plugin names each
+ instruction by its address in its object, and stops a guest that
+ starts a second thread.
+ * `diff` refuses runs that loaded an object at different
+ addresses; runs of another program, or with arguments or an
+ environment of another size, than the first run's; a control
+ that does not repeat the first run's arguments; and a stopped
+ guest's dump. It names sources with LLVM's addr2line.
+ * `traceOf` and `diffOf` run either as a derivation, over a list of
+ runs; `nix/lib.nix` holds them for any package set, with the
+ version the command reports.
* `--object` keeps a taint run's sites (`run`, `read`, and
`traceOf`'s `objects`) to objects whose path contains the given
text, as it keeps a differential run's origins.
+ * The flake's probe check (`checks.<system>.probe`, on Linux) holds
+ both instruments' reports on a known harness to what it does, and
+ on an x86_64 host the differential one on the same harness built
+ for aarch64.
diff --git a/README.md b/README.md
@@ -6,8 +6,8 @@ A Haskell tool that finds where a program's execution depended on a
secret, by running it.
vestigia executes a harness, reports every instruction that branched
-on the secret or computed an address from it, and names each by
-function and source line.
+on the secret, computed an address from it, or divided by or into
+it, and names each by function and source line.
A clean report is not a proof of constant-time execution. It
covers only the paths the harness drove, and the discipline
@@ -39,8 +39,9 @@ can time the same harness. A run that marks nothing is refused.
### Taint: `vestigia run`
`run` executes the harness under valgrind's memcheck with the marked
-bytes undefined, and reports every branch and address that descends
-from them:
+bytes undefined, and reports every branch, address, and integer
+division operand that descends from them (memcheck reports the last
+through vestigia's patch, `nix/memcheck-operand.patch`):
```
$ vestigia run --out trace.json -- ./harness public_key 4
@@ -48,18 +49,23 @@ control 0x4875cd2 MontConfig::from_bigint montgomery_backend.rs:359 x8
control 0x4875cf9 cmp<4> mod.rs:565 x4
...
control 0x4878d4d next<&[u64]> bits.rs:32 x982
-12 secret-dependent site(s); 0 unrelated; 0 fault(s)
+12 secret-dependent site(s) over 1 run(s); 0 unrelated; 0 fault(s)
```
-`vestigia read FILE.xml` reports on a memcheck run made elsewhere.
+memcheck sees only the path a run takes, so trace a harness on
+several secrets: `run --dir DIR` keeps a run (memcheck's XML, where
+the harness's objects loaded, its exit status), and `vestigia read
+DIR...` reports on such runs as one, each site with the runs that
+reached it. `read` takes a memcheck XML file made elsewhere too.
`--object TEXT` keeps the sites in objects whose path contains TEXT.
### Differential traces: `vestigia record` and `vestigia diff`
`record` runs the harness under QEMU with a plugin that summarises,
-per instruction, how often it ran, where it branched, and which
-addresses it touched. Record several runs differing only in the
-secret, and `diff` reports where they diverge:
+per instruction, how often it ran, where it branched, which addresses
+it touched, and, for an integer division, which operands it divided.
+Record several runs differing only in the secret, and `diff` reports
+where they diverge:
```
$ for s in 1 2 3; do
@@ -68,23 +74,28 @@ $ for s in 1 2 3; do
$ vestigia record --dump control -- ./harness public_key 2 1
$ vestigia diff --object libpenumbra_audit --control control \
> --out diff.json run-*
-control 0xe9d6 Element::vartime_compress_to_field sign.rs:11 ...
-address 0x152c8 Fq::sqrt_ratio_zeta invsqrt.rs:113 ...
+control 0xe9d6 abs<Fq> sign.rs:11 ...
+address 0x152c8 Fq::sqrt_ratio_zeta invsqrt.rs:113 ...
...
-44 origin(s) over 3 run(s); 1383 instruction(s) downstream; 0 unsteady ...
+40 origin(s) over 3 run(s); 1387 instruction(s) downstream; 0 unsteady ...
```
An *origin* is a branch whose outcomes differ between runs, in
-proportion or in order, or an instruction whose addresses differ.
-Each names the runs that behaved alike there. Instructions that
-merely ran a different number of times are listed as downstream, and
-every instruction some run executed is listed as coverage.
+proportion or in order (`control`), an instruction whose addresses
+differ (`address`), or a division, whose time depends on its
+operands, on other operands (`operand`). Each names the runs that
+behaved alike there, and the calls that reached it, which the plugin
+keeps as a shadow stack, as memcheck gives a site its callers.
+Instructions that merely ran a different number of times are listed
+as downstream, as are returns whose targets differ, which go where
+their calls sent them; and every instruction some run executed is
+listed as coverage.
* `--control DUMP` repeats the first run's secret; whatever differs
between the two is *unsteady* and kept out of the origins.
* `--designed DUMP` is a run whose secret was chosen to reach a
particular path. It counts toward control origins and coverage,
- never toward address origins.
+ never toward address or operand origins.
* `--object TEXT` keeps the report to matching objects.
`record` disables address-space randomisation and seeds the guest's
@@ -96,13 +107,22 @@ arena, large blocks from the heap), and `diff` refuses runs that
loaded an object at different addresses. A guest reading
`/dev/urandom` still reads the host's.
+`record` appends to its dump how the run was made: the program and
+its arguments, the size of the guest's environment, and the exit
+status, which the report gives for each run. `diff` refuses a run of
+another program, or with arguments of another number or length, or an
+environment of another size, than the first run's, each of which lays
+the guest's stack out apart; and a control that does not repeat the
+first run's arguments.
+
### As derivations
The flake's `lib.<system>` holds `traceOf` and `diffOf`, which run
-either instrument as a derivation; an `x86_64-linux` run executes on
-any builder for that system, and its report is cached. `diffOf`
-repeats the first run as its control. `nix/lib.nix` holds the same
-for a consumer's own nixpkgs, beside `version`.
+either instrument as a derivation over a list of runs; an
+`x86_64-linux` run executes on any builder for that system, and its
+report is cached. `diffOf` repeats the first run as its control.
+`nix/lib.nix` holds the same for a consumer's own nixpkgs, beside
+`version`.
```nix
vestigia.lib.x86_64-linux.diffOf {
@@ -113,8 +133,8 @@ vestigia.lib.x86_64-linux.diffOf {
}
```
-The output holds `trace.json` (`vestigia/trace-v1`) or `diff.json`
-(`vestigia/diff-v2`), the raw memcheck XML or plugin dumps, what the
+The output holds `trace.json` (`vestigia/trace-v2`) or `diff.json`
+(`vestigia/diff-v3`), the runs kept or the plugin's dumps, what the
harness printed, and the wall time.
## Two instruments
@@ -135,23 +155,36 @@ ppad-poly1305, and ppad-secp256k1.
* What a function is meant to reveal (a comparison's result, a
public key) must be marked public, or it is reported.
* valgrind and QEMU's user mode run on Linux; elsewhere vestigia only
- reads their reports. QEMU traces other ISAs differentially, but
+ reads their reports. `record` runs an x86_64 or aarch64 harness on
+ either host, choosing QEMU by the program's ELF header, but
memcheck needs a native host.
-* The plugin assumes a single-threaded guest, and runs compared by
- `diff` must differ only in the secret, argument lengths included.
+* The plugin records one guest thread: a guest that starts a second
+ is stopped, and its dump refused. Runs compared by `diff` must
+ differ only in the secret; it checks their arguments and
+ environments, not what the harness reads beyond them.
+* An address origin can be an address that an earlier secret branch
+ moved, a heap block or stack frame laid out apart, rather than one
+ computed from the secret.
+* Divisions alone are read for their operands. Floating-point
+ division and square root, and multiplication on cores that time it
+ by its operands, are left to a timing instrument.
* A GHC harness wants `-with-rtsopts=-xr1G -V0`, against the
- runtime's terabyte reservation and its interval timer.
-* Source lines need line tables, and sites assume an object's file
- offsets are its virtual addresses, as GNU ld and lld emit them.
+ runtime's terabyte reservation and its interval timer. GHC calls
+ and returns by jumping, so its origins have no callers, and a
+ return to a continuation is not known as a return.
+* Source lines need line tables.
## Development
You'll require [Nix][nixos] with [flake][flake] support enabled.
Enter a development shell with `nix develop`, then `cabal build` and
-`cabal test`. The spikes under `etc/spike` run on an `x86_64-linux`
-builder:
+`cabal test`. The probe check runs `etc/probe/harness.c` under both
+instruments, and the same harness built for aarch64 differentially,
+holding each report to what the harness does; it and the spikes under
+`etc/spike` run on an `x86_64-linux` builder:
```
+$ nix build .#checks.x86_64-linux.probe
$ nix build --impure -f etc/spike/penumbra traces
```
diff --git a/app/Main.hs b/app/Main.hs
@@ -16,34 +16,44 @@ module Main (
import Control.Exception (IOException, try)
import Control.Monad (unless, when)
import qualified Data.ByteString as BS
+import Data.Char (toUpper)
+import qualified Data.Map.Strict as M
+import Data.Foldable (for_)
import Data.Version (showVersion)
+import qualified GHC.Foreign as GF
+import GHC.IO.Encoding (getFileSystemEncoding)
import Numeric (showHex)
import qualified Data.Text as T
import qualified Data.Text.Encoding as TE
import qualified Data.Text.Encoding.Error as TEE
import qualified Data.Text.IO as TIO
-import System.Directory (getTemporaryDirectory, removeFile)
+import System.Directory
+ (createDirectoryIfMissing, doesDirectoryExist, doesFileExist,
+ getTemporaryDirectory, removeFile)
import System.Environment (getArgs, getEnvironment, lookupEnv)
import System.Exit (ExitCode(..), exitWith)
-import System.FilePath (takeFileName)
-import System.IO (hClose, hPutStrLn, openTempFile, stderr)
+import System.FilePath (takeFileName, (</>))
+import Text.Read (readMaybe)
+import System.IO
+ (IOMode(..), hClose, hPutStrLn, openTempFile, stderr, withBinaryFile)
import System.Process (proc, waitForProcess, withCreateProcess)
import qualified System.Process as P
import Paths_vestigia (version)
import Vestigia.Diff
- (diffDesigned, divergenceJson, divergenceSummary, dvOrigins,
- inObject, inOffset, layoutApart, readDump, restrictTo)
+ (Dump(..), Kind(..), Named(..), Run(..), diffDesigned, divergenceJson,
+ divergenceSummary, dvCallers, dvOrigins, inObject, inOffset, inPc,
+ layoutApart, readDump, restrictTo, runApart)
import Vestigia.Json (encode)
import Vestigia.Layout (fixLayout)
-import Vestigia.Memcheck (readMemcheck)
+import Vestigia.Memcheck (Memcheck, readMemcheck)
import Vestigia.Symbol (symbolize)
import Vestigia.Trace
- (readObjects, sitesIn, trace, traceJson, traceSummary, withObjects)
+ (Taint(..), readObjects, sitesIn, trace, traceJson, traceSummary)
data Opts = Opts {
oValgrind :: !(Maybe FilePath)
- , oXml :: !(Maybe FilePath)
+ , oDir :: !(Maybe FilePath)
, oOut :: !(Maybe FilePath)
, oQemu :: !(Maybe FilePath)
, oPlugin :: !(Maybe FilePath)
@@ -63,8 +73,8 @@ main = do
Right (_, []) -> usage "run: no program given"
Left e -> usage e
("read" : rest) -> case options rest of
- Right (o, [ xml ]) -> readXml o xml
- Right _ -> usage "read: one XML file expected"
+ Right (o, runs@(_ : _)) -> readRuns o runs
+ Right _ -> usage "read: a run or memcheck XML file expected"
Left e -> usage e
("record" : rest) -> case options rest of
Right (o, prog : progArgs) -> record o prog progArgs
@@ -82,9 +92,9 @@ usage e = do
hPutStrLn stderr ("vestigia: " <> e)
hPutStrLn stderr $ unlines
[ "usage:"
- , " vestigia run [--valgrind PATH] [--xml FILE] [--out FILE] \
+ , " vestigia run [--valgrind PATH] [--dir DIR] [--out FILE] \
\[--object TEXT]... -- PROGRAM [ARG...]"
- , " vestigia read [--out FILE] [--object TEXT]... FILE.xml"
+ , " vestigia read [--out FILE] [--object TEXT]... RUN..."
, " vestigia record [--qemu PATH] [--plugin PATH] --dump FILE \
\-- PROGRAM [ARG...]"
, " vestigia diff [--out FILE] [--addr2line PATH] \
@@ -92,20 +102,25 @@ usage e = do
\DUMP DUMP..."
, ""
, "run executes PROGRAM under memcheck, which reports every"
- , "branch and address that depended on bytes the program marked"
- , "secret (vestigia.h), and writes the report (vestigia/trace-v1)."
+ , "branch, address, and division that depended on bytes the"
+ , "program marked secret (vestigia.h), and writes the report"
+ , "(vestigia/trace-v2); --dir keeps the run in DIR. read reports"
+ , "on runs kept so, or memcheck XML files made elsewhere, as one."
, "valgrind is --valgrind, else $VESTIGIA_VALGRIND, else on PATH."
, "--object keeps sites in objects whose path contains TEXT."
, ""
, "record executes PROGRAM under QEMU with vestigia's plugin and"
- , "dumps its leakage trace per instruction; diff compares dumps"
- , "of runs that differ only in a secret and reports where they"
- , "diverge (vestigia/diff-v1), naming sources with addr2line."
+ , "dumps its leakage trace per instruction, with how it was run;"
+ , "diff compares dumps of runs that differ only in a secret and"
+ , "reports where they diverge (vestigia/diff-v3), naming sources"
+ , "with addr2line."
, "--object keeps origins in objects whose path contains TEXT;"
, "--control names a run repeating the first run's secret, and"
, "what differs in it is unsteady, not an origin."
- , "qemu, the plugin, and addr2line default to $VESTIGIA_QEMU,"
- , "$VESTIGIA_PLUGIN, and $VESTIGIA_ADDR2LINE."
+ , "QEMU is the one for PROGRAM's architecture: --qemu, else"
+ , "$VESTIGIA_QEMU_X86_64 or $VESTIGIA_QEMU_AARCH64, else"
+ , "qemu-x86_64 or qemu-aarch64 on PATH. The plugin and addr2line"
+ , "default to $VESTIGIA_PLUGIN and $VESTIGIA_ADDR2LINE."
]
exitWith (ExitFailure 2)
@@ -117,7 +132,7 @@ options = go (Opts Nothing Nothing Nothing Nothing Nothing Nothing
go o xs = case xs of
("--" : rest) -> Right (o, rest)
("--valgrind" : p : rest) -> go o { oValgrind = Just p } rest
- ("--xml" : p : rest) -> go o { oXml = Just p } rest
+ ("--dir" : p : rest) -> go o { oDir = Just p } rest
("--out" : p : rest) -> go o { oOut = Just p } rest
("--qemu" : p : rest) -> go o { oQemu = Just p } rest
("--plugin" : p : rest) -> go o { oPlugin = Just p } rest
@@ -134,8 +149,12 @@ options = go (Opts Nothing Nothing Nothing Nothing Nothing Nothing
-- the settings every trace runs under: origins tracked so a
-- secret's descendants are known as such, no limit on contexts,
--- the precise definedness checks optimised code needs, and no
--- leak report
+-- the precise definedness checks optimised code needs, every
+-- register (the instruction pointer among them) brought up to date
+-- at each instruction of a program's own code, so that a site that
+-- touches no memory, a division by a register, is named by its own
+-- address rather than the last memory access before it, and no leak
+-- report
memcheckArgs :: FilePath -> [String]
memcheckArgs xml =
[ "--tool=memcheck"
@@ -145,26 +164,35 @@ memcheckArgs xml =
, "--error-limit=no"
, "--num-callers=24"
, "--expensive-definedness-checks=yes"
+ , "--px-file-backed=allregs-at-each-insn"
, "--leak-check=no"
, "--child-silent-after-fork=yes"
]
+-- a run kept in a directory (run --dir): memcheck's XML, the objects
+-- the harness's first mark wrote (vestigia.h), and the harness's
+-- exit status
+runXml, runObjects, runExit :: FilePath -> FilePath
+runXml d = d </> "memcheck.xml"
+runObjects d = d </> "objects"
+runExit d = d </> "exit"
+
run :: Opts -> FilePath -> [String] -> IO ()
run o prog progArgs = do
env <- lookupEnv "VESTIGIA_VALGRIND"
let valgrind = maybe (maybe "valgrind" id env) id (oValgrind o)
- (xml, temporary) <- case oXml o of
- Just p -> pure (p, False)
+ (xml, objects) <- case oDir o of
+ Just d -> do
+ createDirectoryIfMissing True d
+ writeFile (runObjects d) ""
+ pure (runXml d, runObjects d)
Nothing -> do
tmp <- getTemporaryDirectory
(p, h) <- openTempFile tmp "vestigia.xml"
hClose h
- pure (p, True)
- -- where the harness's loader put its objects, which the
- -- harness's first mark writes (vestigia.h)
- tmp <- getTemporaryDirectory
- (objects, oh) <- openTempFile tmp "vestigia-objects"
- hClose oh
+ (q, oh) <- openTempFile tmp "vestigia-objects"
+ hClose oh
+ pure (p, q)
environment <- getEnvironment
r <- try (withCreateProcess
(proc valgrind (memcheckArgs xml <> (prog : progArgs)))
@@ -178,44 +206,79 @@ run o prog progArgs = do
<> show (e :: IOException))
exitWith (ExitFailure 2)
Right c -> pure c
- otext <- TIO.readFile objects
- os <- case readObjects otext of
+ t <- case oDir o of
+ Just d -> do
+ writeFile (runExit d) (show (exitStatus code) <> "\n")
+ readRun d
+ Nothing -> do
+ os <- markedObjects objects
+ mc <- readXml xml
+ removeFile objects
+ removeFile xml
+ pure (Taint "run" mc os (Just (exitStatus code)))
+ report o [ t ]
+
+exitStatus :: ExitCode -> Int
+exitStatus c = case c of
+ ExitSuccess -> 0
+ ExitFailure n -> n
+
+-- runs kept by run --dir, or memcheck XML files made elsewhere, of
+-- which nothing more is known
+readRuns :: Opts -> [FilePath] -> IO ()
+readRuns o paths = do
+ ts <- traverse (\p -> do
+ kept <- doesDirectoryExist p
+ if kept
+ then readRun p
+ else do
+ mc <- readXml p
+ pure (Taint (T.pack (takeFileName p)) mc [] Nothing))
+ paths
+ report o ts
+
+readRun :: FilePath -> IO Taint
+readRun d = do
+ os <- markedObjects (runObjects d)
+ mc <- readXml (runXml d)
+ known <- doesFileExist (runExit d)
+ exit <- if known
+ then fmap (readMaybe . takeWhile (/= '\n')) (readFile (runExit d))
+ else pure Nothing
+ pure (Taint (T.pack (takeFileName d)) mc os exit)
+
+-- the objects a run's harness reported where it marked its secret;
+-- none written, no secret marked: a run that found nothing because
+-- nothing was secret is no evidence, and is refused
+markedObjects :: FilePath -> IO [(Integer, T.Text)]
+markedObjects p = do
+ t <- TIO.readFile p
+ case readObjects t of
Left e -> do
- hPutStrLn stderr ("vestigia: " <> objects <> ": " <> e)
+ hPutStrLn stderr ("vestigia: " <> p <> ": " <> e)
exitWith (ExitFailure 2)
- Right v -> pure v
- removeFile objects
- -- no objects written, no secret marked: a run that found nothing
- -- because nothing was secret is no evidence, and is refused
- when (null os) $ do
- hPutStrLn stderr "vestigia: the harness marked no secret \
- \(vestigia_secret was never called on any bytes); its run \
- \says nothing"
- exitWith (ExitFailure 2)
- report o (Just (exitCode code)) os xml
- if temporary then removeFile xml else pure ()
- where
- exitCode c = case c of
- ExitSuccess -> 0
- ExitFailure n -> n
-
-readXml :: Opts -> FilePath -> IO ()
-readXml o xml = report o Nothing [] xml
+ Right [] -> do
+ hPutStrLn stderr ("vestigia: " <> p <> ": the harness marked \
+ \no secret (vestigia_secret was never called on any bytes); \
+ \its run says nothing")
+ exitWith (ExitFailure 2)
+ Right os -> pure os
-report :: Opts -> Maybe Int -> [(Integer, T.Text)] -> FilePath -> IO ()
-report o exit os xml = do
+readXml :: FilePath -> IO Memcheck
+readXml xml = do
bytes <- BS.readFile xml
- let txt = TE.decodeUtf8With TEE.lenientDecode bytes
- case readMemcheck txt of
+ case readMemcheck (TE.decodeUtf8With TEE.lenientDecode bytes) of
Left e -> do
hPutStrLn stderr ("vestigia: " <> xml <> ": " <> e)
exitWith (ExitFailure 2)
- Right mc -> do
- let tr = sitesIn (oObjects o) (withObjects os (trace mc))
- doc = encode
- (traceJson (T.pack (showVersion version)) exit tr)
- maybe (TIO.putStr doc) (\p -> TIO.writeFile p doc) (oOut o)
- TIO.hPutStr stderr (traceSummary tr)
+ Right mc -> pure mc
+
+report :: Opts -> [Taint] -> IO ()
+report o ts = do
+ let tr = sitesIn (oObjects o) (trace ts)
+ doc = encode (traceJson (T.pack (showVersion version)) tr)
+ maybe (TIO.putStr doc) (\p -> TIO.writeFile p doc) (oOut o)
+ TIO.hPutStr stderr (traceSummary tr)
-- a tool named by its option, else its environment variable, else
-- the given default
@@ -235,7 +298,10 @@ record o prog progArgs = do
hPutStrLn stderr "vestigia: address randomisation could not be \
\turned off; runs would differ in layout, and so everywhere"
exitWith (ExitFailure 2)
- qemu <- tool (oQemu o) "VESTIGIA_QEMU" "qemu-x86_64"
+ -- QEMU's user mode runs the programs of one architecture
+ isa <- machineOf prog
+ qemu <- tool (oQemu o) ("VESTIGIA_QEMU_" <> fmap toUpper isa)
+ ("qemu-" <> isa)
plugin <- tool (oPlugin o) "VESTIGIA_PLUGIN" "libvestigia-qemu.so"
-- QEMU maps the guest's libraries and heap in its own address
-- space, wherever its own allocations leave room, and those vary
@@ -249,22 +315,67 @@ record o prog progArgs = do
let tunables = "GLIBC_TUNABLES"
host = "glibc.malloc.arena_max=1:glibc.malloc.mmap_threshold="
<> "33554432"
+ own = lookup tunables environment
guest = maybe [ "-U", tunables ]
- (\v -> [ "-E", tunables <> "=" <> v ]) (lookup tunables environment)
+ (\v -> [ "-E", tunables <> "=" <> v ]) own
+ others = filter ((/= tunables) . fst) environment
r <- try (withCreateProcess
((proc qemu (guest
<> [ "-seed", "0"
, "-plugin", plugin <> ",out=" <> dump, prog ]
<> progArgs))
- { P.env = Just ((tunables, host)
- : filter ((/= tunables) . fst) environment) })
+ { P.env = Just ((tunables, host) : others) })
(\_ _ _ ph -> waitForProcess ph))
case r of
Left e -> do
hPutStrLn stderr ("vestigia: cannot run " <> qemu <> ": "
<> show (e :: IOException))
exitWith (ExitFailure 2)
- Right c -> exitWith c
+ Right c -> do
+ -- how the run was made, by which diff tells runs that differ
+ -- in the secret alone from runs laid out apart: the guest's
+ -- environment is QEMU's, with its own tunables restored
+ appendRun dump (prog : progArgs)
+ (others <> [ (tunables, v) | Just v <- [ own ] ]) c
+ exitWith c
+
+-- the architecture an ELF program is built for, as QEMU names its
+-- user-mode emulators: the header's machine, at byte 18
+machineOf :: FilePath -> IO String
+machineOf prog = do
+ r <- try (withBinaryFile prog ReadMode (\h -> BS.hGet h 20))
+ case fmap BS.unpack r of
+ Right (0x7f : 0x45 : 0x4c : 0x46 : _ : 1 : rest)
+ | [ 0x3e, 0 ] <- drop 12 rest -> pure "x86_64"
+ | [ 0xb7, 0 ] <- drop 12 rest -> pure "aarch64"
+ Right _ -> unknown "not an x86_64 or aarch64 ELF program"
+ Left e -> unknown (show (e :: IOException))
+ where
+ unknown why = do
+ hPutStrLn stderr ("vestigia: " <> prog <> ": " <> why
+ <> "; QEMU's user mode runs one")
+ exitWith (ExitFailure 2)
+
+-- append a run's record to its dump (Vestigia.Diff.readDump): its
+-- arguments' bytes, its environment's variables and the bytes they
+-- take, and its exit status
+appendRun :: FilePath -> [String] -> [(String, String)] -> ExitCode
+ -> IO ()
+appendRun dump args env code = do
+ enc <- getFileSystemEncoding
+ let bytes s = GF.withCStringLen enc s BS.packCStringLen
+ as <- traverse bytes args
+ es <- traverse (\(k, v) -> bytes (k <> "=" <> v)) env
+ appendFile dump $ unlines $
+ [ unwords ("A" : [ concatMap byte (BS.unpack a) | not (BS.null a) ])
+ | a <- as ]
+ <> [ "N " <> showHex (length es) "" <> " "
+ <> showHex (sum (fmap ((+ 1) . BS.length) es)) ""
+ , "X " <> show (exitStatus code) ]
+ where
+ byte w = case showHex w "" of
+ [ d ] -> [ '0', d ]
+ ds -> ds
diff :: Opts -> [FilePath] -> IO ()
diff o paths = do
@@ -272,6 +383,28 @@ diff o paths = do
dumps <- traverse readOne paths
controls <- traverse readOne (oControls o)
designed <- traverse readOne (oDesigned o)
+ -- every run with how it was made: the declared, the designed, then
+ -- the controls. Runs made apart differ by more than the secret,
+ -- and are refused, not compared
+ named <- traverse (\(p, k, d) -> case dpRun d of
+ Just r -> pure (p, Named (T.pack (takeFileName p)) k r)
+ Nothing -> refuse (p <> " holds no record of how it was run \
+ \(vestigia record appends one), so nothing says what it ran"))
+ (zip3 (paths <> oDesigned o <> oControls o)
+ (fmap (const DeclaredRun) paths
+ <> fmap (const DesignedRun) (oDesigned o)
+ <> fmap (const ControlRun) (oControls o))
+ (dumps <> designed <> controls))
+ case named of
+ ((p0, first) : rest) -> for_ rest $ \(p, n) -> do
+ for_ (runApart (nmRun first) (nmRun n)) $ \why ->
+ refuse (p <> " " <> why <> " (" <> p0 <> "); runs compared \
+ \must differ in the secret alone")
+ when (nmKind n == ControlRun
+ && rnArguments (nmRun n) /= rnArguments (nmRun first)) $
+ refuse (p <> " is a control, but does not repeat the \
+ \arguments of " <> p0 <> ", the run it controls")
+ [] -> pure ()
-- runs laid out apart differ wherever they touch memory, not by
-- the secret: such runs are refused, not compared
case zip paths dumps of
@@ -291,20 +424,23 @@ diff o paths = do
[] -> pure ()
let dv = restrictTo (oObjects o)
(diffDesigned controls dumps designed)
- places <- symbolize addr2line
+ places <- symbolize addr2line $
[ (obj, inOffset i) | (_, i) <- dvOrigins dv
, Just obj <- [ inObject i ] ]
- -- a run is named by its dump's file name, the declared first
- let names = fmap (T.pack . takeFileName) (paths <> oDesigned o)
- doc = encode
- (divergenceJson (T.pack (showVersion version)) names places dv)
+ -- the calls that reached each origin
+ <> [ (obj, a) | (_, i) <- dvOrigins dv
+ , Just (stacks, _) <- [ M.lookup (inPc i) (dvCallers dv) ]
+ , calls <- stacks, (Just obj, a) <- calls ]
+ let doc = encode (divergenceJson (T.pack (showVersion version))
+ (fmap snd named) places dv)
maybe (TIO.putStr doc) (\p -> TIO.writeFile p doc) (oOut o)
TIO.hPutStr stderr (divergenceSummary places dv)
where
readOne p = do
bytes <- BS.readFile p
case readDump (TE.decodeUtf8With TEE.lenientDecode bytes) of
- Left e -> do
- hPutStrLn stderr ("vestigia: " <> p <> ": " <> e)
- exitWith (ExitFailure 2)
+ Left e -> refuse (p <> ": " <> e)
Right d -> pure d
+ refuse e = do
+ hPutStrLn stderr ("vestigia: " <> e)
+ exitWith (ExitFailure 2)
diff --git a/etc/probe/harness.c b/etc/probe/harness.c
@@ -0,0 +1,102 @@
+/*
+ * harness.c: the harness the flake's probe check runs under both
+ * instruments.
+ *
+ * Copyright (c) 2026 Jared Tobin
+ * License: MIT
+ *
+ * Its secret, the first argument in hex (of one width for every
+ * secret, so that runs lay out alike), reaches a loop's bound, a
+ * table index, which of two calls a helper returns to, a dividend,
+ * a divisor, and, on a path the third secret alone takes, another
+ * table index; a constant-time select reaches none of them.
+ */
+#include <stdio.h>
+#include <stdlib.h>
+
+#include "vestigia.h"
+
+static unsigned char table[256];
+static volatile unsigned modulus = 3329;
+
+__attribute__((noinline)) unsigned branchy(unsigned s) {
+ unsigned r = 0;
+ for (unsigned i = 0; i < (s & 7); i++) r += i;
+ return r;
+}
+
+__attribute__((noinline)) unsigned lookup(unsigned s) {
+ return table[s & 0xff];
+}
+
+__attribute__((noinline)) unsigned leaf(unsigned x) {
+ return x * 3u + 1u;
+}
+
+/* leaf runs eight times whatever the secret, but returns to one call
+ or the other as the secret's bits say */
+__attribute__((noinline)) unsigned calls(unsigned s) {
+ unsigned r = 0;
+ for (unsigned i = 0; i < 8; i++) {
+ if ((s >> i) & 1u) r += leaf(i);
+ else r ^= leaf(i + 1u);
+ }
+ return r;
+}
+
+/* a secret divided by a public modulus, the divisor in a register */
+__attribute__((noinline)) unsigned divide(unsigned s) {
+#if defined(__x86_64__)
+ unsigned q, r;
+ __asm__ volatile("divl %4"
+ : "=a"(q), "=d"(r)
+ : "a"(s * 2654435761u), "d"(0u), "r"(modulus));
+ return q ^ r;
+#else
+ return (s * 2654435761u) / modulus;
+#endif
+}
+
+/* a public value divided by a secret, which x86_64 reads from memory
+ as the division's operand */
+__attribute__((noinline)) unsigned divide_memory(unsigned s) {
+ unsigned d = (s & 0xffu) | 1u;
+#if defined(__x86_64__)
+ unsigned q, r;
+ __asm__ volatile("divl %4"
+ : "=a"(q), "=d"(r)
+ : "a"(1000003u), "d"(0u), "m"(d));
+ return q ^ r;
+#else
+ return 1000003u / d;
+#endif
+}
+
+/* a table index on a path one secret takes */
+__attribute__((noinline)) unsigned rare(unsigned s) {
+ if ((s & 0xffu) == 0xc3u) return table[(s >> 1) & 0xffu];
+ return 0;
+}
+
+__attribute__((noinline)) unsigned ct(unsigned s, unsigned p) {
+ unsigned m = 0u - (p & 1u);
+ return (s & m) | (~s & ~m);
+}
+
+int main(int argc, char **argv) {
+ unsigned s = (unsigned)strtoul(argc > 1 ? argv[1] : "0", NULL, 16);
+ unsigned out[7];
+ for (int i = 0; i < 256; i++) table[i] = (unsigned char)i;
+ vestigia_secret(&s, sizeof s);
+ out[0] = branchy(s);
+ out[1] = lookup(s);
+ out[2] = calls(s);
+ out[3] = divide(s);
+ out[4] = divide_memory(s);
+ out[5] = rare(s);
+ out[6] = ct(s, 1);
+ vestigia_public(out, sizeof out);
+ printf("%u %u %u %u %u %u %u\n", out[0], out[1], out[2], out[3],
+ out[4], out[5], out[6]);
+ return 0;
+}
diff --git a/etc/probe/threads.c b/etc/probe/threads.c
@@ -0,0 +1,16 @@
+/*
+ * threads.c: a guest that starts a second thread, which the plugin
+ * stops rather than record.
+ *
+ * Copyright (c) 2026 Jared Tobin
+ * License: MIT
+ */
+#include <pthread.h>
+
+static void *work(void *p) { return p; }
+
+int main(void) {
+ pthread_t t;
+ if (pthread_create(&t, NULL, work, NULL) != 0) return 1;
+ return pthread_join(t, NULL);
+}
diff --git a/etc/spike/penumbra/default.nix b/etc/spike/penumbra/default.nix
@@ -36,7 +36,7 @@ let
traceOf = build: lib: root: vestigia.lib.${system}.traceOf {
name = "penumbra-${build}-${root}";
harness = "${harnessFor lib}/bin/harness";
- args = [ root "4" ];
+ runs = [ [ root "4" ] ];
};
roots = [ "public_key" "key_agreement" "spend_auth_sign" ];
diff --git a/etc/spike/poly1305/default.nix b/etc/spike/poly1305/default.nix
@@ -49,7 +49,7 @@ let
path = vestigia.lib.${system}.traceOf {
name = "poly1305-${name}";
harness = bin;
- args = [ "4" "1" ];
+ runs = [ [ "4" "1" ] ];
}; }
{ name = "diff";
path = vestigia.lib.${system}.diffOf {
diff --git a/etc/spike/secp256k1/default.nix b/etc/spike/secp256k1/default.nix
@@ -53,7 +53,7 @@ let
path = vestigia.lib.${system}.traceOf {
name = "secp256k1-${name}";
harness = bin;
- args = [ "2" "1" ];
+ runs = [ [ "2" "1" ] ];
}; }
{ name = "diff";
path = vestigia.lib.${system}.diffOf {
diff --git a/flake.nix b/flake.nix
@@ -35,7 +35,13 @@
inherit (v) traceOf diffOf valgrindDev version;
};
- checks.default = hpkgs.vestigia;
+ checks = {
+ default = hpkgs.vestigia;
+ }
+ # both instruments run Linux programs
+ // lib.optionalAttrs linux {
+ probe = import ./nix/probe.nix { inherit pkgs; vestigia = v; };
+ };
devShells.default = hpkgs.shellFor {
packages = p: [ p.vestigia ];
diff --git a/lib/Vestigia/Diff.hs b/lib/Vestigia/Diff.hs
@@ -10,7 +10,8 @@
-- Where runs that differ only in a secret differ. Each run is a
-- leakage trace summarised per instruction (the QEMU plugin's
-- dump): how often each instruction ran, how often it transferred
--- to each target, and a fingerprint of the addresses it touched.
+-- to each target, a fingerprint of the addresses it touched, and,
+-- for an integer division, a fingerprint of its operands.
--
-- A branch whose outcome did not depend on the secret takes each
-- of its transfers in the same proportion however often it runs; a
@@ -21,9 +22,14 @@
-- taking each transfer as often, in another order: the plugin keeps
-- an order-sensitive fingerprint of what followed each instruction.
-- An instruction run equally often in every run whose addresses
--- differ computed one from the secret: an `address` origin. Every
+-- differ computed one from the secret: an `address` origin. A
+-- division, whose time depends on its operands, run equally often
+-- on other operands is an `operand` origin. Every
-- other instruction run a different number of times sits where
--- control had already diverged: it is downstream.
+-- control had already diverged: it is downstream. So is a return
+-- whose transfers differ, however often it ran: it goes where the
+-- call before it sent it, so its outcomes differ only because
+-- control had diverged before the call.
--
-- Unlike memcheck's taint, this sees what control flow does to
-- data as well as what data does: a value chosen by a secret
@@ -42,8 +48,9 @@
-- only in the secret, so an instruction's addresses differing in one
-- of them says nothing about the secret. A designed run counts toward
-- the control origins (a branch whose outcomes shift under it chose
--- by the secret) and what was executed, never toward the address
--- origins, which only runs alike in all but the secret can show.
+-- by the secret) and what was executed, never toward the address or
+-- operand origins, which only runs alike in all but the secret can
+-- show.
--
-- What every run executed, per object, is reported beside: the
-- instructions the chosen secrets exercised, and so, against what
@@ -52,14 +59,20 @@
-- Each origin names how the runs behaved there: the runs alike at
-- it, grouped (taking each transfer in the same proportion, at a
-- control origin; touching the same addresses, at an address
--- origin), and the runs that never reached it. Whether two runs
+-- origin; dividing the same operands, at an operand origin), and the
+-- runs that never reached it. Whether two runs
-- that differed there both had their secrets accepted is the
-- reader's to say, from what each run returned.
module Vestigia.Diff (
Insn(..)
+ , Run(..)
, Dump(..)
, readDump
+ , callsOf
+ , runApart
+ , Kind(..)
+ , Named(..)
, Origin(..)
, Divergence(..)
, diffDumps
@@ -72,16 +85,22 @@ module Vestigia.Diff (
, divergenceSummary
) where
+import Control.Monad (foldM, unless)
+import qualified Data.ByteString as BS
import qualified Data.List as L
import qualified Data.Map.Strict as M
import qualified Data.Set as S
import qualified Data.Text as T
+import qualified Data.Text.Encoding as TE
+import qualified Data.Text.Encoding.Error as TEE
import Numeric (readHex, showHex)
+import Text.Read (readMaybe)
import Vestigia.Json
import Vestigia.Symbol (Place(..))
--- | One instruction of a run.
+-- | One instruction of a run: its run-time address, and its object
+-- and address there, where the object's program headers place it.
data Insn = Insn {
inPc :: !Integer
, inCount :: !Integer
@@ -93,44 +112,173 @@ data Insn = Insn {
, inOffset :: !Integer
} deriving (Eq, Show)
--- | One run: its instructions by address, and its transfers by
--- source, each a count per target.
+-- | How a run was made, as `vestigia record` appends it to the
+-- plugin's dump: the program and its arguments, as the bytes it
+-- passed them; the variables of the environment the guest was
+-- given, and the bytes they take; and the run's exit status.
+data Run = Run {
+ rnArguments :: ![BS.ByteString]
+ , rnEnvironment :: !(Integer, Integer)
+ , rnStatus :: !Integer
+ } deriving (Eq, Show)
+
+-- | One run: its instructions by address, its transfers by source,
+-- each a count per target, the instructions that return, the
+-- divisions' operands, fingerprinted, the contexts calls made (each
+-- by the context it was made in and the call's address, 0 being
+-- the program's own), the contexts each instruction ran in (with
+-- whether it ran in more than the plugin kept), and how the run
+-- was made, where its dump says.
data Dump = Dump {
dpInsns :: !(M.Map Integer Insn)
, dpTransfers :: !(M.Map Integer (M.Map Integer Integer))
+ , dpReturns :: !(S.Set Integer)
+ , dpOperands :: !(M.Map Integer T.Text)
+ , dpContexts :: !(M.Map Integer (Integer, Integer))
+ , dpCallers :: !(M.Map Integer (Bool, [Integer]))
+ , dpRun :: !(Maybe Run)
} deriving (Eq, Show)
-- | Read a plugin dump. A dump in which no instruction ran records
-- no run (the plugin writes every instruction the guest executed),
--- and is refused rather than compared as one that did nothing.
+-- and is refused rather than compared as one that did nothing, as
+-- is the dump of a guest the plugin stopped for starting a second
+-- thread, or one whose contexts do not chain back to the
+-- program's own. The record `vestigia record` appends (an @A@ line
+-- per argument, its bytes in hex; @N@, the environment's variables
+-- and bytes, in hex; @X@, the exit status, in decimal) is read
+-- whole or not at all.
readDump :: T.Text -> Either String Dump
-readDump t = go (T.lines t) M.empty M.empty
+readDump t = do
+ d <- foldM line (Dump M.empty M.empty S.empty M.empty M.empty M.empty
+ Nothing, [], Nothing, Nothing) (T.lines t)
+ let (dump, as, env, st) = d
+ cx = dpContexts dump
+ unless (any ((> 0) . inCount) (M.elems (dpInsns dump))) $
+ Left "no instruction ran: the run was not recorded"
+ -- each context made in one made before it, so that its calls end
+ unless (and [ c' < c && (c' == 0 || M.member c' cx)
+ | (c, (c', _)) <- M.toList cx ]) $
+ Left "a context made in one not made before it"
+ unless (and [ c == 0 || M.member c cx
+ | (_, cs) <- M.elems (dpCallers dump), c <- cs ]) $
+ Left "an instruction run in a context the dump does not make"
+ r <- record (reverse as) env st
+ pure dump { dpRun = r }
where
- go ls is es = case ls of
- []
- | any ((> 0) . inCount) (M.elems is) -> pure (Dump is es)
- | otherwise ->
- Left "no instruction ran: the run was not recorded"
- (l : rest) -> case T.words l of
- [ "I", pc, n, a, fp, ord, obj, off ] -> do
- i <- Insn <$> unhex pc <*> unhex n <*> unhex a <*> pure fp
- <*> pure ord
- <*> pure (if obj == "-" then Nothing else Just obj)
- <*> unhex off
- go rest (M.insert (inPc i) i is) es
- [ "E", from, to, n ] -> do
- f <- unhex from
- k <- unhex to
- c <- unhex n
- go rest is (M.insertWith M.union f (M.singleton k c) es)
- [] -> go rest is es
- _ -> Left ("an unreadable dump line: " <> T.unpack l)
+ line (d, as, env, st) l = case T.words l of
+ [ "I", pc, n, a, fp, ord, obj, off ] -> do
+ i <- Insn <$> unhex pc <*> unhex n <*> unhex a <*> pure fp
+ <*> pure ord
+ <*> pure (if obj == "-" then Nothing else Just obj)
+ <*> unhex off
+ pure (d { dpInsns = M.insert (inPc i) i (dpInsns d) }, as, env
+ , st)
+ [ "E", from, to, n ] -> do
+ f <- unhex from
+ k <- unhex to
+ c <- unhex n
+ pure (d { dpTransfers = M.insertWith M.union f (M.singleton k c)
+ (dpTransfers d) }, as, env, st)
+ [ "R", pc ] -> do
+ r <- unhex pc
+ pure (d { dpReturns = S.insert r (dpReturns d) }, as, env, st)
+ [ "D", pc, fp ] -> do
+ k <- unhex pc
+ pure (d { dpOperands = M.insert k fp (dpOperands d) }, as, env
+ , st)
+ [ "C", c, caller, call ] -> do
+ v <- (,) <$> unhex caller <*> unhex call
+ k <- unhex c
+ pure (d { dpContexts = M.insert k v (dpContexts d) }, as, env
+ , st)
+ ("K" : pc : partial : cs@(_ : _)) -> do
+ k <- unhex pc
+ p <- case partial of
+ "0" -> pure False
+ "1" -> pure True
+ _ -> Left ("an unreadable dump line: " <> T.unpack l)
+ xs <- traverse unhex cs
+ pure (d { dpCallers = M.insert k (p, xs) (dpCallers d) }, as
+ , env, st)
+ [ "T", _ ] ->
+ Left "the guest started a second thread, which a trace \
+ \cannot record: the run was stopped"
+ [ "A" ] -> pure (d, BS.empty : as, env, st)
+ [ "A", h ] -> do
+ b <- unhexBytes h
+ pure (d, b : as, env, st)
+ [ "N", n, b ] -> do
+ v <- (,) <$> unhex n <*> unhex b
+ pure (d, as, Just v, st)
+ [ "X", x ] -> case readMaybe (T.unpack x) of
+ Just v -> pure (d, as, env, Just v)
+ Nothing -> Left ("not an exit status: " <> T.unpack x)
+ [] -> pure (d, as, env, st)
+ _ -> Left ("an unreadable dump line: " <> T.unpack l)
+ record as env st = case (as, env, st) of
+ ([], Nothing, Nothing) -> pure Nothing
+ (_ : _, Just e, Just x) -> pure (Just (Run as e x))
+ _ -> Left "an incomplete record of the run"
unhex x = case readHex (T.unpack x) of
[ (v, "") ] -> pure v
_ -> Left ("not hexadecimal: " <> T.unpack x)
+ unhexBytes h
+ | odd (T.length h) = Left ("not hexadecimal bytes: " <> T.unpack h)
+ | otherwise =
+ BS.pack <$> traverse (fmap fromInteger . unhex) (T.chunksOf 2 h)
+
+-- | The calls that made a context, innermost first, at most 24 of
+-- them (as memcheck keeps): each by its object and address there,
+-- or by its run-time address where the run names no object for it.
+callsOf :: Dump -> Integer -> [(Maybe T.Text, Integer)]
+callsOf d = go (24 :: Int)
+ where
+ go n c
+ | n <= 0 || c == 0 = []
+ | otherwise = case M.lookup c (dpContexts d) of
+ Just (caller, pc) -> site pc : go (n - 1) caller
+ Nothing -> []
+ site pc = case M.lookup pc (dpInsns d) of
+ Just i | Just o <- inObject i -> (Just o, inOffset i)
+ _ -> (Nothing, pc)
+
+-- | Why a run cannot be set beside the first as differing from it in
+-- the secret alone, if it cannot: it ran another program, its
+-- arguments differ from the first run's in number or length, or it
+-- was given an environment of another size. Each lays the guest's
+-- stack out apart, and so every address on it.
+runApart :: Run -> Run -> Maybe String
+runApart first r
+ | take 1 (rnArguments r) /= take 1 (rnArguments first) =
+ Just "ran another program than the first run"
+ | fmap BS.length (rnArguments r)
+ /= fmap BS.length (rnArguments first) =
+ Just "has arguments that differ from the first run's in number \
+ \or length"
+ | rnEnvironment r /= rnEnvironment first =
+ Just "was given an environment of another size than the first \
+ \run's"
+ | otherwise = Nothing
+
+-- | What a run is to a comparison: declared, designed for a path, or
+-- a control repeating the first run's secret.
+data Kind =
+ DeclaredRun
+ | DesignedRun
+ | ControlRun
+ deriving (Eq, Show)
+
+-- | A run as the report names it: by its dump's file name, with what
+-- it is to the comparison and how it was made.
+data Named = Named {
+ nmName :: !T.Text
+ , nmKind :: !Kind
+ , nmRun :: !Run
+ } deriving (Eq, Show)
-- | Where a run loaded each object it executed: any of its
--- instructions' addresses less its offset in the object.
+-- instructions' run-time addresses less its address in the object.
loadBases :: Dump -> M.Map T.Text Integer
loadBases d = M.fromList
[ (o, inPc i - inOffset i)
@@ -152,6 +300,7 @@ layoutApart a b =
data Origin =
ControlOrigin
| AddressOrigin
+ | OperandOrigin
deriving (Eq, Ord, Show)
-- | Where the runs differ: the origins, each an instruction run
@@ -161,7 +310,8 @@ data Divergence = Divergence {
dvOrigins :: ![(Origin, Insn)]
-- | at each origin, the runs alike there, grouped, and the runs
-- that never reached it, as indices into the declared runs
- -- then the designed (an address origin's, the declared alone)
+ -- then the designed (an address or operand origin's, the
+ -- declared alone)
, dvBehaviour :: !(M.Map (Origin, Integer) ([[Int]], [Int]))
, dvDownstream :: ![Insn]
, dvUnsteady :: ![Insn]
@@ -170,6 +320,10 @@ data Divergence = Divergence {
, dvDesigned :: !Int
-- | the offsets some run, control or not, executed, by object
, dvExecuted :: !(M.Map T.Text (S.Set Integer))
+ -- | at each origin, the distinct chains of calls that reached it
+ -- in the declared and designed runs, at most 16 of them, and
+ -- whether there were more than those
+ , dvCallers :: !(M.Map Integer ([[(Maybe T.Text, Integer)]], Bool))
} deriving (Eq, Show)
-- | Compare runs, uncontrolled.
@@ -184,8 +338,9 @@ diffControlled :: [Dump] -> [Dump] -> Divergence
diffControlled cs ds = diffDesigned cs ds []
-- | Compare runs, given controls and runs designed to reach particular
--- paths. The address origins are the declared runs' alone; the
--- control origins and what was executed are every run's.
+-- paths. The address and operand origins are the declared runs'
+-- alone; the control origins and what was executed are every
+-- run's.
diffDesigned :: [Dump] -> [Dump] -> [Dump] -> Divergence
diffDesigned cs ds xs = Divergence {
dvOrigins = L.sortOn (inPc . snd) origins
@@ -205,8 +360,17 @@ diffDesigned cs ds xs = Divergence {
, i <- M.elems (dpInsns d)
, inCount i > 0
, Just obj <- [ inObject i ] ]
+ , dvCallers = M.fromList
+ [ (inPc i, callersAt (inPc i)) | (_, i) <- origins ]
}
where
+ callersAt pc =
+ let found = [ (partial, fmap (callsOf d) ks)
+ | d <- runs
+ , Just (partial, ks) <- [ M.lookup pc (dpCallers d) ] ]
+ stacks = L.nub (concatMap snd found)
+ in (take 16 stacks, any fst found || length stacks > 16)
+
-- what differs between the first run and a repeat of its secret
unsteady = case ds of
(d : _) -> S.unions (fmap (differing d) cs)
@@ -219,10 +383,11 @@ diffDesigned cs ds xs = Divergence {
ib = M.lookup pc (dpInsns b)
ta = M.lookup pc (dpTransfers a)
tb = M.lookup pc (dpTransfers b)
- , fmap sig ia /= fmap sig ib || ta /= tb ]
+ , fmap sig ia /= fmap sig ib || ta /= tb
+ || M.lookup pc (dpOperands a) /= M.lookup pc (dpOperands b) ]
sig i = (inCount i, inFingerprint i, inOrder i)
- origins = [ o | o@(_, i) <- controls <> addresses
+ origins = [ o | o@(_, i) <- controls <> addresses <> operands
, not (inPc i `S.member` unsteady) ]
-- every run, the declared first
@@ -230,7 +395,7 @@ diffDesigned cs ds xs = Divergence {
-- how the runs behaved at an origin: those that ran it, grouped
-- by what they did there, and those that never ran it. Only the
- -- declared runs speak to an address.
+ -- declared runs speak to an address or an operand.
behaviourAt o pc = case o of
ControlOrigin ->
( classes outcomesAlike
@@ -241,6 +406,10 @@ diffDesigned cs ds xs = Divergence {
AddressOrigin ->
( classes (==) [ (k, inFingerprint i) | (k, _, i) <- ranIn ds ]
, absentIn ds )
+ OperandOrigin ->
+ ( classes (==)
+ [ (k, M.lookup pc (dpOperands d)) | (k, d, _) <- ranIn ds ]
+ , absentIn ds )
where
ranIn rs = [ (k, d, i) | (k, d) <- zip [ 0 .. ] rs
, Just i <- [ M.lookup pc (dpInsns d) ]
@@ -290,10 +459,18 @@ diffDesigned cs ds xs = Divergence {
(r : rest) -> not (all (outcomesAlike r) rest)
[] -> False
- controlPcs = S.filter divergent transferSources
- addressPcs = S.fromList [ inPc i | (_, i) <- addresses ]
- downstream = ((pcs `S.difference` steady) `S.difference` controlPcs)
- `S.difference` addressPcs
+ -- a return goes where its call sent it: downstream, never an
+ -- origin, whatever its outcomes
+ returns = S.unions (fmap dpReturns runs)
+ divergentPcs = S.filter divergent transferSources
+ controlPcs = divergentPcs `S.difference` returns
+ -- the address and operand origins
+ dataPcs = S.fromList [ inPc i | (_, i) <- addresses <> operands ]
+ downstream =
+ (((pcs `S.difference` steady)
+ `S.union` (divergentPcs `S.intersection` returns))
+ `S.difference` controlPcs)
+ `S.difference` dataPcs
controls =
[ (ControlOrigin, i)
@@ -309,6 +486,16 @@ diffDesigned cs ds xs = Divergence {
, Just i <- [ firstInsn pc ]
, inAccesses i > 0 ]
+ -- a division run equally often in every declared run, on other
+ -- operands in one
+ operands =
+ [ (OperandOrigin, i)
+ | pc <- S.toAscList steadyDeclared
+ , let fps = [ M.lookup pc (dpOperands d) | d <- ds ]
+ , any (/= Nothing) fps
+ , not (alike fps)
+ , Just i <- [ firstInsn pc ] ]
+
-- | Only the origins, what was executed, and what ran downstream, in
-- objects whose path contains one of the given texts.
restrictTo :: [T.Text] -> Divergence -> Divergence
@@ -329,22 +516,35 @@ originText :: Origin -> T.Text
originText o = case o of
ControlOrigin -> "control"
AddressOrigin -> "address"
+ OperandOrigin -> "operand"
--- | The report: @vestigia/diff-v2@. Runs are named as given, the
--- declared then the designed.
+-- | The report: @vestigia/diff-v3@. Runs are given the declared,
+-- then the designed, then the controls, and an origin names the
+-- runs alike at it by the first two. An origin's stacks are its own
+-- frames then its calls', innermost first, each frame with the
+-- object and address of the instruction it names, as memcheck's
+-- are in a taint report.
divergenceJson
- :: T.Text -> [T.Text] -> M.Map (T.Text, Integer) [Place] -> Divergence
+ :: T.Text -> [Named] -> M.Map (T.Text, Integer) [Place] -> Divergence
-> Value
-divergenceJson version names places dv = Object
- [ ("schema", String "vestigia/diff-v2")
+divergenceJson version runs places dv = Object
+ [ ("schema", String "vestigia/diff-v3")
, ("tool", Object [ ("name", String "vestigia")
, ("version", String version) ])
- , ("runs", Number (toInteger (dvRuns dv)))
- , ("controls", Number (toInteger (dvControls dv)))
- , ("designed", Number (toInteger (dvDesigned dv)))
+ , ("runs", Array
+ [ Object
+ [ ("name", String (nmName r))
+ , ("kind", String (kindText (nmKind r)))
+ , ("arguments", Array
+ [ String (TE.decodeUtf8With TEE.lenientDecode a)
+ | a <- rnArguments (nmRun r) ])
+ , ("status", Number (rnStatus (nmRun r)))
+ ]
+ | r <- runs ])
, ("summary", Object
[ ("control", count ControlOrigin)
, ("address", count AddressOrigin)
+ , ("operand", count OperandOrigin)
, ("downstream", Number (toInteger (length (dvDownstream dv))))
, ("unsteady", Number (toInteger (length (dvUnsteady dv))))
])
@@ -356,12 +556,19 @@ divergenceJson version names places dv = Object
, ("offset", String (hex (inOffset i)))
, ("count", Number (inCount i))
, ("frames", Array (fmap placeJson (placesOf i)))
+ , ("stacks", Array
+ [ Array (located (inObject i, inOffset i)
+ <> concatMap located calls)
+ | calls <- stacks ])
+ , ("partial", Bool partial)
, ("groups", Array (fmap (Array . fmap named) groups))
, ("absent", Array (fmap named absent))
]
| (o, i) <- dvOrigins dv
, let (groups, absent) = M.findWithDefault ([], []) (o, inPc i)
- (dvBehaviour dv) ])
+ (dvBehaviour dv)
+ (stacks, partial) = M.findWithDefault ([], False) (inPc i)
+ (dvCallers dv) ])
, ("downstream", Object
[ (obj, Array (fmap (String . hex) (S.toAscList offs)))
| (obj, offs) <- M.toList (M.fromListWith S.union
@@ -373,6 +580,11 @@ divergenceJson version names places dv = Object
| (o, xs) <- M.toList (dvExecuted dv) ])
]
where
+ names = [ nmName r | r <- runs, nmKind r /= ControlRun ]
+ kindText k = case k of
+ DeclaredRun -> "declared"
+ DesignedRun -> "designed"
+ ControlRun -> "control"
count o = Number (toInteger (length
[ () | (o', _) <- dvOrigins dv, o' == o ]))
named k = case drop k names of
@@ -390,6 +602,21 @@ divergenceJson version names places dv = Object
, ("file", maybe Null String (plFile p))
, ("line", maybe Null (Number . toInteger) (plLine p))
]
+ -- an instruction's frames, innermost first, each with where the
+ -- instruction is; one unnamed frame where nothing names it
+ located (mo, a) =
+ let at = [ ("object", maybe Null String mo)
+ , ("offset", String (hex a)) ]
+ ps = case mo of
+ Just obj -> M.findWithDefault [] (obj, a) places
+ Nothing -> []
+ in case ps of
+ [] -> [ Object (at <> [ ("function", Null), ("file", Null)
+ , ("line", Null) ]) ]
+ _ -> [ case placeJson p of
+ Object kvs -> Object (at <> kvs)
+ other -> other
+ | p <- ps ]
-- | One line per origin, innermost frame first, for a terminal.
divergenceSummary
diff --git a/lib/Vestigia/Symbol.hs b/lib/Vestigia/Symbol.hs
@@ -7,20 +7,26 @@
-- License: MIT
-- Maintainer: Jared Tobin <jared@ppad.tech>
--
--- Naming an instruction by its source: binutils' addr2line over an
--- object's debug information, inlined frames included. An object's
--- file offset is taken as its virtual address, which holds for the
--- executable segments of what GNU ld and lld emit; an object that
--- does not satisfy it names its sites wrongly, not silently: its
--- functions will not match its disassembly.
+-- Naming an instruction by its source: an addr2line over an
+-- object's debug information, inlined frames included, at the
+-- instruction's address in the object (where the object's program
+-- headers place it, as its disassembly does). LLVM's names each
+-- inlined frame by its own function, and an address no symbol covers
+-- by none, where binutils' gives the innermost frame the name of the
+-- function it was inlined into, and code without debug information
+-- (a GHC program's) the name of whatever function precedes it. LLVM
+-- leaves a legacy Rust symbol as an Itanium demangler does, its
+-- escapes and hash in place, which are undone here.
module Vestigia.Symbol (
Place(..)
, symbolize
, parseAddr2line
+ , rustLegacy
) where
import Control.Exception (IOException, try)
+import Data.Char (chr, isHexDigit)
import qualified Data.Map.Strict as M
import qualified Data.Text as T
import Numeric (readHex, showHex)
@@ -36,7 +42,7 @@ data Place = Place {
, plLine :: !(Maybe Int)
} deriving (Eq, Show)
--- | The source of each offset, per object, by one addr2line call
+-- | The source of each address, per object, by one addr2line call
-- per object. An object addr2line cannot read names nothing.
symbolize
:: FilePath -> [(T.Text, Integer)]
@@ -84,7 +90,7 @@ parseAddr2line = go . T.lines
place f loc =
let (file, line) = location loc
in Place {
- plFunction = if f == "??" then Nothing else Just f
+ plFunction = if f == "??" then Nothing else Just (rustLegacy f)
, plFile = file
, plLine = line
}
@@ -98,3 +104,40 @@ parseAddr2line = go . T.lines
, case readMaybe (T.unpack n) of
Just 0 -> Nothing
other -> other )
+
+-- | A legacy Rust symbol, as an Itanium demangler leaves it, as
+-- rustc-demangle gives it: its hash dropped, each path segment's
+-- escapes undone. Any other name is left as it is.
+--
+-- >>> rustLegacy "a::_$LT$impl$u20$b..C$GT$::f::h346fee1681a4f34f"
+-- "a::<impl b::C>::f"
+rustLegacy :: T.Text -> T.Text
+rustLegacy t = case T.breakOnEnd "::" t of
+ (pre, h) | not (T.null pre), hash h ->
+ T.intercalate "::"
+ (fmap segment (T.splitOn "::" (T.dropEnd 2 pre)))
+ _ -> t
+ where
+ hash h = case T.uncons h of
+ Just ('h', ds) -> T.length ds == 16 && T.all isHexDigit ds
+ _ -> False
+ segment g = T.pack (unescape (T.unpack
+ (maybe g ("$" <>) (T.stripPrefix "_$" g))))
+ unescape cs = case cs of
+ '$' : rest
+ | (code, '$' : more) <- break (== '$') rest
+ , Just r <- escape code -> r <> unescape more
+ '.' : '.' : more -> "::" <> unescape more
+ c : more -> c : unescape more
+ [] -> []
+ escape code = case code of
+ "SP" -> Just "@"
+ "BP" -> Just "*"
+ "RF" -> Just "&"
+ "LT" -> Just "<"
+ "GT" -> Just ">"
+ "LP" -> Just "("
+ "RP" -> Just ")"
+ "C" -> Just ","
+ 'u' : h | [ (n, "") ] <- readHex h -> Just [ chr n ]
+ _ -> Nothing
diff --git a/lib/Vestigia/Trace.hs b/lib/Vestigia/Trace.hs
@@ -11,19 +11,27 @@
-- whose undefined value was created by a client request descends
-- from a byte the harness marked secret, so it is a site where the
-- execution depended on the secret: a branch (`control`), an
--- address computed from it (`address`), or a system call handed
--- it (`syscall`). Every other uninitialised read is kept apart as
--- `unrelated`, and memory errors as `faults`: neither says
--- anything about the secret. Leak reports say nothing about the
--- execution and are dropped.
+-- address computed from it (`address`), an integer division's
+-- operand (`operand`, from vestigia's patched memcheck), or a
+-- system call handed it (`syscall`). Every other uninitialised read
+-- is kept apart as `unrelated`, and memory errors as `faults`:
+-- neither says anything about the secret. Leak reports say nothing
+-- about the execution and are dropped.
+--
+-- memcheck sees the path a run took, so runs of one harness on
+-- several secrets are read together: a site is one instruction and
+-- class however many runs reached it, with the runs that did. Where
+-- a run's objects are known, a site is named by its address in its
+-- object, so runs that loaded an object apart still agree on it.
module Vestigia.Trace (
Class(..)
+ , Taint(..)
+ , Located(..)
, Site(..)
, Trace(..)
, trace
, sitesIn
- , withObjects
, readObjects
, objectOffset
, traceJson
@@ -43,34 +51,55 @@ import Vestigia.Memcheck
data Class =
Control
| Address
+ | Operand
| Syscall
deriving (Eq, Ord, Show)
--- | One instruction that depended on a secret, with every stack
--- that reached it.
+-- | One run under memcheck: its name, what memcheck reported, where
+-- the harness's loader put each object (its load bias and path,
+-- as the harness reported them; none for a report made
+-- elsewhere), and the harness's exit status, where known.
+data Taint = Taint {
+ tnName :: !T.Text
+ , tnMemcheck :: !Memcheck
+ , tnObjects :: ![(Integer, T.Text)]
+ , tnExit :: !(Maybe Int)
+ } deriving (Eq, Show)
+
+-- | A frame, with its address in its object where its run's objects
+-- say.
+data Located = Located {
+ lcFrame :: !Frame
+ , lcOffset :: !(Maybe Integer)
+ } deriving (Eq, Show)
+
+-- | One instruction that depended on a secret: where, as the first
+-- run to reach it saw it; how many times, over every run; the runs
+-- that reached it, as indices into the runs; and every stack that
+-- did.
data Site = Site {
siClass :: !Class
- , siFrame :: !Frame
+ , siAt :: !Located
, siCount :: !Int
- , siStacks :: ![[Frame]]
+ , siRuns :: ![Int]
+ , siStacks :: ![[Located]]
} deriving (Eq, Show)
--- | A run's sites, in the order first reported, and what memcheck
--- reported that says nothing about the secret.
+-- | Runs' sites, in the order first reported, and what memcheck
+-- reported that says nothing about the secret, each with the
+-- index of the run that reported it.
data Trace = Trace {
- trRun :: !Memcheck
+ trRuns :: ![Taint]
, trSites :: ![Site]
- , trUnrelated :: ![MemError]
- , trFaults :: ![MemError]
- -- | where the harness's loader put each object: its load bias
- -- and path, as the harness reported them
- , trObjects :: ![(Integer, T.Text)]
+ , trUnrelated :: ![(Int, MemError)]
+ , trFaults :: ![(Int, MemError)]
} deriving (Eq, Show)
classText :: Class -> T.Text
classText c = case c of
Control -> "control"
Address -> "address"
+ Operand -> "operand"
Syscall -> "syscall"
-- what a secret-originated error says about the execution
@@ -78,46 +107,59 @@ classify :: MemError -> Maybe Class
classify e = case (meOrigin e, meKind e) of
(ClientRequest _, "UninitCondition") -> Just Control
(ClientRequest _, "UninitValue") -> Just Address
+ (ClientRequest _, "UninitOperand") -> Just Operand
(ClientRequest _, "SyscallParam") -> Just Syscall
_ -> Nothing
uninitialised :: MemError -> Bool
-uninitialised e =
- meKind e `elem` [ "UninitCondition", "UninitValue", "SyscallParam" ]
+uninitialised e = meKind e `elem`
+ [ "UninitCondition", "UninitValue", "UninitOperand", "SyscallParam" ]
--- | The run's leakage. Sites are one per instruction and class:
+-- | The runs' leakage. Sites are one per instruction and class:
-- memcheck reports one context per distinct stack, and the
--- instruction is what depended on the secret, whatever called
--- it.
-trace :: Memcheck -> Trace
-trace mc = Trace {
- trRun = mc
+-- instruction is what depended on the secret, whatever called it
+-- and in whichever run.
+trace :: [Taint] -> Trace
+trace ts = Trace {
+ trRuns = ts
, trSites =
[ Site {
siClass = c
- , siFrame = top
- , siCount = sum (fmap (meCount . snd) xs)
- , siStacks = L.nub (fmap (meStack . snd) xs)
+ , siAt = at
+ , siCount = sum [ meCount e | (_, e, _) <- xs ]
+ , siRuns = L.nub [ k | (k, _, _) <- xs ]
+ , siStacks = L.nubBy (\a b -> fmap ident a == fmap ident b)
+ [ st | (_, _, st) <- xs ]
}
- | k@(c, _) <- order
- , Just xs@((top, _) : _) <- [ M.lookup k grouped ] ]
+ | key@(c, _) <- L.nub (fmap fst tagged)
+ , Just xs@((_, _, at : _) : _) <- [ M.lookup key grouped ] ]
, trUnrelated =
- [ e | e <- mcErrors mc, uninitialised e
- , classify e == Nothing ]
+ [ (k, e) | (k, t) <- runs, e <- mcErrors (tnMemcheck t)
+ , uninitialised e, classify e == Nothing ]
, trFaults =
- [ e | e <- mcErrors mc, not (uninitialised e)
- , not ("Leak_" `T.isPrefixOf` meKind e) ]
- , trObjects = []
+ [ (k, e) | (k, t) <- runs, e <- mcErrors (tnMemcheck t)
+ , not (uninitialised e)
+ , not ("Leak_" `T.isPrefixOf` meKind e) ]
}
where
+ runs = zip [ 0 .. ] ts
tagged =
- [ ((c, top), e)
- | e <- mcErrors mc
+ [ ((c, ident top), (k, e, st))
+ | (k, t) <- runs
+ , e <- mcErrors (tnMemcheck t)
, Just c <- [ classify e ]
- , (top : _) <- [ meStack e ] ]
- order = L.nub (fmap (\((c, top), _) -> (c, frIp top)) tagged)
+ , let st = fmap (locate (tnObjects t)) (meStack e)
+ , (top : _) <- [ st ] ]
grouped = M.fromListWith (flip (<>))
- [ ((c, frIp top), [ (top, e) ]) | ((c, top), e) <- tagged ]
+ [ (key, [ v ]) | (key, v) <- tagged ]
+ -- an instruction is its address in its object where that is
+ -- known, else its address in the run
+ ident (Located f off) =
+ ( frObj f, maybe (Left (frIp f)) Right off, frFn f, frFile f
+ , frLine f )
+
+locate :: [(Integer, T.Text)] -> Frame -> Located
+locate os f = Located f (objectOffset os f)
-- | Only the sites in objects whose path contains one of the given
-- texts, as a differential run keeps its origins; every site when
@@ -127,15 +169,10 @@ sitesIn ts tr
| null ts = tr
| otherwise = tr { trSites = filter inside (trSites tr) }
where
- inside s = case frObj (siFrame s) of
+ inside s = case frObj (lcFrame (siAt s)) of
Just o -> any (`T.isInfixOf` o) ts
Nothing -> False
--- | The trace with the harness's map of its objects, by which each
--- frame is named by its address in its object.
-withObjects :: [(Integer, T.Text)] -> Trace -> Trace
-withObjects os tr = tr { trObjects = os }
-
-- | The objects file the harness's first mark writes: a load bias
-- (hex) and a path per line.
--
@@ -166,65 +203,71 @@ objectOffset os f = do
(x : _) -> x
[] -> p
--- | The report: @vestigia/trace-v1@.
-traceJson :: T.Text -> Maybe Int -> Trace -> Value
-traceJson version exit tr = Object
- [ ("schema", String "vestigia/trace-v1")
+-- | The report: @vestigia/trace-v2@.
+traceJson :: T.Text -> Trace -> Value
+traceJson version tr = Object
+ [ ("schema", String "vestigia/trace-v2")
, ("tool", Object [ ("name", String "vestigia")
, ("version", String version) ])
- , ("valgrind", maybe Null String (mcVersion mc))
- , ("command", Array (fmap String (mcCommand mc)))
- , ("finished", Bool (mcFinished mc))
- , ("exit", maybe Null (Number . toInteger) exit)
+ , ("runs", Array
+ [ Object
+ [ ("name", String (tnName t))
+ , ("valgrind", maybe Null String (mcVersion mc))
+ , ("command", Array (fmap String (mcCommand mc)))
+ , ("finished", Bool (mcFinished mc))
+ , ("exit", maybe Null (Number . toInteger) (tnExit t))
+ , ("objects", Array
+ [ Object [ ("base", String (hex b)), ("path", String p) ]
+ | (b, p) <- tnObjects t ])
+ ]
+ | t <- trRuns tr, let mc = tnMemcheck t ])
, ("summary", Object
[ ("control", count Control)
, ("address", count Address)
+ , ("operand", count Operand)
, ("syscall", count Syscall)
, ("unrelated", Number (toInteger (length (trUnrelated tr))))
, ("faults", Number (toInteger (length (trFaults tr))))
])
- , ("objects", Array
- [ Object [ ("base", String (hex b)), ("path", String p) ]
- | (b, p) <- trObjects tr ])
- , ("sites", Array (fmap (siteJson os) (trSites tr)))
- , ("unrelated", Array (fmap (errorJson os) (trUnrelated tr)))
- , ("faults", Array (fmap (errorJson os) (trFaults tr)))
+ , ("sites", Array (fmap siteJson (trSites tr)))
+ , ("unrelated", Array (fmap errorJson (trUnrelated tr)))
+ , ("faults", Array (fmap errorJson (trFaults tr)))
]
where
- os = trObjects tr
- mc = trRun tr
count c = Number (toInteger (length
[ () | s <- trSites tr, siClass s == c ]))
+ name k = case drop k (trRuns tr) of
+ (t : _) -> String (tnName t)
+ [] -> String (T.pack (show k))
+ objectsOf k = case drop k (trRuns tr) of
+ (t : _) -> tnObjects t
+ [] -> []
+ siteJson s = Object $
+ [ ("class", String (classText (siClass s))) ]
+ <> locatedFields (siAt s)
+ <> [ ("count", Number (toInteger (siCount s)))
+ , ("runs", Array (fmap name (siRuns s)))
+ , ("stacks", Array [ Array (fmap (Object . locatedFields) st)
+ | st <- siStacks s ])
+ ]
+ errorJson (k, e) = Object
+ [ ("run", name k)
+ , ("kind", String (meKind e))
+ , ("what", String (meWhat e))
+ , ("origin", case meOrigin e of
+ ClientRequest _ -> String "client request"
+ OtherOrigin w _ -> String w
+ NoOrigin -> Null)
+ , ("count", Number (toInteger (meCount e)))
+ , ("stack", Array (fmap (Object . locatedFields
+ . locate (objectsOf k)) (meStack e)))
+ ]
-siteJson :: [(Integer, T.Text)] -> Site -> Value
-siteJson os s = Object $
- [ ("class", String (classText (siClass s))) ]
- <> frameFields os (siFrame s)
- <> [ ("count", Number (toInteger (siCount s)))
- , ("stacks", Array [ Array (fmap (frameJson os) st)
- | st <- siStacks s ])
- ]
-
-errorJson :: [(Integer, T.Text)] -> MemError -> Value
-errorJson os e = Object
- [ ("kind", String (meKind e))
- , ("what", String (meWhat e))
- , ("origin", case meOrigin e of
- ClientRequest _ -> String "client request"
- OtherOrigin w _ -> String w
- NoOrigin -> Null)
- , ("count", Number (toInteger (meCount e)))
- , ("stack", Array (fmap (frameJson os) (meStack e)))
- ]
-
-frameJson :: [(Integer, T.Text)] -> Frame -> Value
-frameJson os = Object . frameFields os
-
-frameFields :: [(Integer, T.Text)] -> Frame -> [(T.Text, Value)]
-frameFields os f =
+locatedFields :: Located -> [(T.Text, Value)]
+locatedFields (Located f off) =
[ ("ip", String (hex (frIp f)))
, ("object", maybe Null String (frObj f))
- , ("offset", maybe Null (String . hex) (objectOffset os f))
+ , ("offset", maybe Null (String . hex) off)
, ("function", maybe Null String (frFn f))
, ("file", maybe Null String (frFile f))
, ("line", maybe Null (Number . toInteger) (frLine f))
@@ -233,21 +276,27 @@ frameFields os f =
hex :: Integer -> T.Text
hex n = "0x" <> T.pack (showHex n "")
--- | One line per site, for a reader at a terminal.
+-- | One line per site, for a reader at a terminal: with how many runs
+-- reached it, where there were several.
traceSummary :: Trace -> T.Text
traceSummary tr = T.unlines $
- [ T.intercalate " "
+ [ T.intercalate " " $
[ classText (siClass s)
- , hex (frIp (siFrame s))
- , maybe "?" id (frFn (siFrame s))
- , location (siFrame s)
+ , hex (frIp f)
+ , maybe "?" id (frFn f)
+ , location f
, "x" <> T.pack (show (siCount s)) ]
- | s <- trSites tr ]
+ <> [ T.pack (show (length (siRuns s))) <> "/"
+ <> T.pack (show runs) <> " runs"
+ | runs > 1 ]
+ | s <- trSites tr, let f = lcFrame (siAt s) ]
<> [ T.pack (show (length (trSites tr))) <> " secret-dependent \
- \site(s); " <> T.pack (show (length (trUnrelated tr)))
+ \site(s) over " <> T.pack (show runs) <> " run(s); "
+ <> T.pack (show (length (trUnrelated tr)))
<> " unrelated; " <> T.pack (show (length (trFaults tr)))
<> " fault(s)" ]
where
+ runs = length (trRuns tr)
location f = case (frFile f, frLine f) of
(Just p, Just l) -> base p <> ":" <> T.pack (show l)
(Just p, Nothing) -> base p
diff --git a/nix/lib.nix b/nix/lib.nix
@@ -16,24 +16,24 @@ let
});
# memcheck runs on Linux only; elsewhere the command can still
- # read a run's XML
+ # read a run's XML. It reports an integer division's undefined
+ # operands (memcheck-operand.patch)
linux = pkgs.stdenv.hostPlatform.isLinux;
- valgrind = pkgs.valgrind;
+ valgrind = pkgs.valgrind.overrideAttrs (o: {
+ patches = (o.patches or [ ]) ++ [ ./memcheck-operand.patch ];
+ });
# the QEMU plugin recording a run's leakage trace per
- # instruction, and the QEMU that runs a harness of this
- # system's ISA under it: user mode alone, its guest's getrandom
- # drawn from the generator -seed fixes (qemu-getrandom.patch)
+ # instruction, and the QEMU that runs a harness under it, for
+ # either ISA, whatever the host's: user mode alone, its guest's
+ # getrandom drawn from the generator -seed fixes
+ # (qemu-getrandom.patch)
qemu = (pkgs.qemu.override {
userOnly = true;
hostCpuTargets = [ "x86_64-linux-user" "aarch64-linux-user" ];
}).overrideAttrs (o: {
patches = (o.patches or [ ]) ++ [ ./qemu-getrandom.patch ];
});
- qemuFor = {
- x86_64 = "${qemu}/bin/qemu-x86_64";
- aarch64 = "${qemu}/bin/qemu-aarch64";
- };
plugin = pkgs.runCommandCC "vestigia-qemu-plugin" {
nativeBuildInputs = [ pkgs.pkg-config ];
buildInputs = [ pkgs.glib ];
@@ -43,9 +43,6 @@ let
$(pkg-config --cflags glib-2.0) -I${qemu}/include \
-o $out/lib/libvestigia-qemu.so ${src}/plugin/vestigia-qemu.c
'';
- isa = builtins.head
- (lib.splitString "-" pkgs.stdenv.hostPlatform.system);
-
# the harness-side header; a harness build also needs
# valgrind's own (valgrindDev)
include = pkgs.runCommand "vestigia-include" { } ''
@@ -54,7 +51,9 @@ let
cp ${src}/include/vestigia.c $out/include/vestigia.c
'';
- # the command, with the valgrind it was built against baked in
+ # the command, with the valgrind it was built against baked in,
+ # and LLVM's addr2line, which reads either ISA's objects and names
+ # inlined frames by their own functions (Vestigia.Symbol)
vestigia = pkgs.runCommand "vestigia" {
nativeBuildInputs = [ pkgs.makeWrapper ];
} ''
@@ -62,37 +61,46 @@ let
makeWrapper ${hpkgs.vestigia}/bin/vestigia $out/bin/vestigia \
${lib.optionalString linux (lib.concatStringsSep " " [
"--set-default VESTIGIA_VALGRIND ${valgrind}/bin/valgrind"
- "--set-default VESTIGIA_QEMU ${qemuFor.${isa}}"
+ "--set-default VESTIGIA_QEMU_X86_64 ${qemu}/bin/qemu-x86_64"
+ "--set-default VESTIGIA_QEMU_AARCH64 ${qemu}/bin/qemu-aarch64"
"--set-default VESTIGIA_PLUGIN"
"${plugin}/lib/libvestigia-qemu.so"
"--set-default VESTIGIA_ADDR2LINE"
- "${pkgs.binutils-unwrapped}/bin/addr2line"
+ "${pkgs.llvm}/bin/llvm-addr2line"
])}
ln -s ${include}/include $out/include
'';
- # one harness run under memcheck, as a derivation: its report,
- # memcheck's XML, and what the harness printed. `objects` keeps
- # sites in objects whose path contains one of them. A harness that
- # fails still leaves a report of what ran; a run vestigia could
- # not read fails the build.
- traceOf = { name, harness, args ? [ ], objects ? [ ] }:
+ # runs of one harness under memcheck, as a derivation: each run
+ # kept (run-K: memcheck's XML, the objects its harness reported,
+ # its exit status, its own report), what each printed, and the
+ # report over all of them. `runs` is a list of argument lists, the
+ # secrets of the trace; memcheck sees only the path a run takes, so
+ # each run adds the sites on its own. `objects` keeps sites in
+ # objects whose path contains one of them. A harness that fails
+ # still leaves a report of what ran; a run vestigia could not read
+ # fails the build.
+ traceOf = { name, harness, runs, objects ? [ ] }:
pkgs.runCommand "vestigia-trace-${name}" { } ''
mkdir -p $out
start=$(date +%s%N)
- set +e
- ${vestigia}/bin/vestigia run \
- --xml $out/memcheck.xml --out $out/trace.json \
+ ${lib.concatImapStrings (k: args: ''
+ set +e
+ ${vestigia}/bin/vestigia run --dir $out/run-${toString k} \
+ --out $out/run-${toString k}/trace.json \
+ -- ${harness} ${lib.escapeShellArgs args} \
+ > $out/stdout-${toString k} 2> $out/stderr-${toString k}
+ echo $? > $out/status-${toString k}
+ set -e
+ '') runs}
+ ${vestigia}/bin/vestigia read --out $out/trace.json \
${lib.concatMapStrings (o: "--object ${lib.escapeShellArg o} ")
- objects}-- ${harness} ${lib.escapeShellArgs args} \
- > $out/stdout 2> $out/stderr
- echo $? > $out/status
- set -e
- echo $(( ($(date +%s%N) - start) / 1000000 )) > $out/milliseconds
- test -s $out/trace.json || {
- cat $out/stderr >&2
+ objects}${lib.concatImapStrings (k: _:
+ "$out/run-${toString k} ") runs} 2> $out/summary || {
+ cat $out/summary >&2
exit 1
}
+ echo $(( ($(date +%s%N) - start) / 1000000 )) > $out/milliseconds
'';
# runs of one harness that differ only in a secret, each
diff --git a/nix/memcheck-operand.patch b/nix/memcheck-operand.patch
@@ -0,0 +1,316 @@
+memcheck lets an undefined operand flow into a division's quotient
+without a word: it reports an undefined value only where it decides a
+branch or forms an address. An integer division takes a time that
+depends on its operands, so a division of or by a secret leaks it,
+and a taint trace should say so.
+
+This adds an error kind, UninitOperand ("Integer division depends on
+uninitialised value(s)", suppressed as "Operand"), with its origin
+tracked as a condition's is, and reports it for each undefined
+operand of every integer division the guest's code is lifted to:
+DivModU/S128to64, 64to32, 64to64, and 32to32 (x86_64's DIV and IDIV
+among them), DivU/S32 and 64 and their E forms (aarch64's UDIV and
+SDIV), and the 128-bit divisions and modulos. Unlike the checks
+before an address or a branch, it leaves the operands undefined
+after reporting them, so the quotient's undefinedness, and what is
+reported downstream of it, is as it would have been.
+
+--- a/memcheck/mc_errors.c
++++ b/memcheck/mc_errors.c
+@@ -63,6 +63,7 @@
+ enum {
+ Err_Value,
+ Err_Cond,
++ Err_Operand,
+ Err_CoreMem,
+ Err_Addr,
+ Err_Jump,
+@@ -108,6 +109,14 @@
+ ExeContext* origin_ec; // filled in later
+ } Cond;
+
++ // Use of an undefined value as an operand of an integer
++ // division, whose time depends on its operands.
++ struct {
++ // Origin info
++ UInt otag; // origin tag
++ ExeContext* origin_ec; // filled in later
++ } Operand;
++
+ // Addressability error in core (signal-handling) operation.
+ // It would be good to get rid of this error kind, merge it with
+ // another one somehow.
+@@ -527,6 +536,26 @@
+ }
+ break;
+
++ case Err_Operand:
++ MC_(any_value_errors) = True;
++ if (xml) {
++ emit( " <kind>UninitOperand</kind>\n" );
++ emit( " <what>Integer division depends"
++ " on uninitialised value(s)</what>\n" );
++ VG_(pp_ExeContext)( VG_(get_error_where)(err) );
++ if (extra->Err.Operand.origin_ec)
++ mc_pp_origin( extra->Err.Operand.origin_ec,
++ extra->Err.Operand.otag & 3 );
++ } else {
++ emit( "Integer division depends"
++ " on uninitialised value(s)\n" );
++ VG_(pp_ExeContext)( VG_(get_error_where)(err) );
++ if (extra->Err.Operand.origin_ec)
++ mc_pp_origin( extra->Err.Operand.origin_ec,
++ extra->Err.Operand.otag & 3 );
++ }
++ break;
++
+ case Err_RegParam:
+ MC_(any_value_errors) = True;
+ if (xml) {
+@@ -936,6 +965,18 @@
+ VG_(maybe_record_error)( tid, Err_Cond, /*addr*/0, /*s*/NULL, &extra );
+ }
+
++void MC_(record_operand_error) ( ThreadId tid, UInt otag )
++{
++ MC_Error extra;
++ tl_assert( MC_(clo_mc_level) >= 2 );
++ if (otag > 0)
++ tl_assert( MC_(clo_mc_level) == 3 );
++ extra.Err.Operand.otag = otag;
++ extra.Err.Operand.origin_ec = NULL; /* Filled in later */
++ VG_(maybe_record_error)( tid, Err_Operand, /*addr*/0, /*s*/NULL,
++ &extra );
++}
++
+ /* --- Called from non-generated code --- */
+
+ /* This is for memory errors in signal-related memory. */
+@@ -1214,6 +1255,7 @@
+ case Err_IllegalMempool:
+ case Err_Overlap:
+ case Err_Cond:
++ case Err_Operand:
+ case Err_ReallocSizeZero:
+ case Err_UnsafeZeroSize:
+ return True;
+@@ -1423,6 +1465,10 @@
+ update_origin( &extra->Err.Cond.origin_ec,
+ extra->Err.Cond.otag );
+ return sizeof(MC_Error);
++ case Err_Operand:
++ update_origin( &extra->Err.Operand.origin_ec,
++ extra->Err.Operand.otag );
++ return sizeof(MC_Error);
+ case Err_RegParam:
+ update_origin( &extra->Err.RegParam.origin_ec,
+ extra->Err.RegParam.otag );
+@@ -1557,6 +1603,9 @@
+ // Undefined value error in conditional.
+ CondSupp,
+
++ // Undefined value error in an integer division's operand.
++ OperandSupp,
++
+ // Unaddressable read/write attempt at given size
+ Addr1Supp, Addr2Supp, Addr4Supp, Addr8Supp, Addr16Supp, Addr32Supp,
+
+@@ -1593,6 +1642,7 @@
+ else if (VG_STREQ(name, "Overlap")) skind = OverlapSupp;
+ else if (VG_STREQ(name, "Mempool")) skind = MempoolSupp;
+ else if (VG_STREQ(name, "Cond")) skind = CondSupp;
++ else if (VG_STREQ(name, "Operand")) skind = OperandSupp;
+ else if (VG_STREQ(name, "Value0")) skind = CondSupp; /* backwards compat */
+ else if (VG_STREQ(name, "Value1")) skind = Value1Supp;
+ else if (VG_STREQ(name, "Value2")) skind = Value2Supp;
+@@ -1739,6 +1789,9 @@
+ case CondSupp:
+ return (ekind == Err_Cond);
+
++ case OperandSupp:
++ return (ekind == Err_Operand);
++
+ case Addr1Supp: su_szB = 1; goto addr_case;
+ case Addr2Supp: su_szB = 2; goto addr_case;
+ case Addr4Supp: su_szB = 4; goto addr_case;
+@@ -1822,6 +1875,7 @@
+ case Err_Overlap: return "Overlap";
+ case Err_Leak: return "Leak";
+ case Err_Cond: return "Cond";
++ case Err_Operand: return "Operand";
+ case Err_FishyValue: return "FishyValue";
+ case Err_ReallocSizeZero: return "ReallocZero";
+ case Err_BadAlign: return "BadAlign";
+--- a/memcheck/mc_include.h
++++ b/memcheck/mc_include.h
+@@ -551,6 +551,7 @@
+ void MC_(record_address_error) ( ThreadId tid, Addr a, Int szB,
+ Bool isWrite );
+ void MC_(record_cond_error) ( ThreadId tid, UInt otag );
++void MC_(record_operand_error) ( ThreadId tid, UInt otag );
+ void MC_(record_value_error) ( ThreadId tid, Int szB, UInt otag );
+ void MC_(record_jump_error) ( ThreadId tid, Addr a );
+
+@@ -773,6 +774,7 @@
+ VG_REGPARM(1) void MC_(helperc_value_check4_fail_w_o) ( UWord );
+ VG_REGPARM(1) void MC_(helperc_value_check1_fail_w_o) ( UWord );
+ VG_REGPARM(1) void MC_(helperc_value_check0_fail_w_o) ( UWord );
++VG_REGPARM(1) void MC_(helperc_operand_check_fail_w_o) ( UWord );
+
+ /* And call these ones instead to report an uninitialised value error
+ but with no origin available. */
+@@ -781,6 +783,7 @@
+ VG_REGPARM(0) void MC_(helperc_value_check4_fail_no_o) ( void );
+ VG_REGPARM(0) void MC_(helperc_value_check1_fail_no_o) ( void );
+ VG_REGPARM(0) void MC_(helperc_value_check0_fail_no_o) ( void );
++VG_REGPARM(0) void MC_(helperc_operand_check_fail_no_o) ( void );
+
+ /* V-bits load/store helpers */
+ VG_REGPARM(1) void MC_(helperc_STOREV64be) ( Addr, ULong );
+--- a/memcheck/mc_main.c
++++ b/memcheck/mc_main.c
+@@ -5751,6 +5751,11 @@
+ }
+
+ VG_REGPARM(1)
++void MC_(helperc_operand_check_fail_w_o) ( UWord origin ) {
++ MC_(record_operand_error) ( VG_(get_running_tid)(), (UInt)origin );
++}
++
++VG_REGPARM(1)
+ void MC_(helperc_value_check1_fail_w_o) ( UWord origin ) {
+ MC_(record_value_error) ( VG_(get_running_tid)(), 1, (UInt)origin );
+ }
+@@ -5775,6 +5780,11 @@
+ VG_REGPARM(0)
+ void MC_(helperc_value_check0_fail_no_o) ( void ) {
+ MC_(record_cond_error) ( VG_(get_running_tid)(), 0/*origin*/ );
++}
++
++VG_REGPARM(0)
++void MC_(helperc_operand_check_fail_no_o) ( void ) {
++ MC_(record_operand_error) ( VG_(get_running_tid)(), 0/*origin*/ );
+ }
+
+ VG_REGPARM(0)
+--- a/memcheck/mc_translate.c
++++ b/memcheck/mc_translate.c
+@@ -1772,6 +1772,57 @@
+ }
+
+
++/* Check the supplied *original* atoms, the operands of an integer
++ division, for undefinedness, and emit a complaint for each that is
++ undefined. A division takes a time that depends on its operands,
++ so an undefined operand is reported as its own kind of error
++ (Err_Operand), apart from a value used as an address or a
++ condition. Unlike complainIfUndefined, the atoms are not then
++ marked defined: the quotient carries its operands' undefinedness
++ on, as it would had nothing been reported. */
++static void complainIfOperandsUndefined ( MCEnv* mce,
++ IRAtom* atom1, IRAtom* atom2 )
++{
++ IRAtom* atoms[2] = { atom1, atom2 };
++ Int k;
++
++ if (MC_(clo_mc_level) == 1)
++ return;
++
++ for (k = 0; k < 2; k++) {
++ IRAtom* vatom;
++ IRAtom* origin;
++ IRDirty* di;
++
++ tl_assert(isOriginalAtom(mce, atoms[k]));
++ vatom = expr2vbits( mce, atoms[k], HuOth );
++ tl_assert(isShadowAtom(mce, vatom));
++
++ if (MC_(clo_mc_level) == 3) {
++ origin = schemeE( mce, atoms[k] );
++ if (mce->hWordTy == Ity_I64) {
++ origin = assignNew( 'B', mce, Ity_I64,
++ unop(Iop_32Uto64, origin) );
++ }
++ di = unsafeIRDirty_0_N(
++ 1, "MC_(helperc_operand_check_fail_w_o)",
++ VG_(fnptr_to_fnentry)(
++ &MC_(helperc_operand_check_fail_w_o) ),
++ mkIRExprVec_1(origin) );
++ } else {
++ di = unsafeIRDirty_0_N(
++ 0, "MC_(helperc_operand_check_fail_no_o)",
++ VG_(fnptr_to_fnentry)(
++ &MC_(helperc_operand_check_fail_no_o) ),
++ mkIRExprVec_0() );
++ }
++ di->guard = mkPCastTo( mce, Ity_I1, vatom );
++ setHelperAnns( mce, di );
++ stmt( 'V', mce, IRStmt_Dirty(di) );
++ }
++}
++
++
+ /*------------------------------------------------------------*/
+ /*--- Shadowing PUTs/GETs, and indexed variants thereof ---*/
+ /*------------------------------------------------------------*/
+@@ -4153,6 +4204,7 @@
+ case Iop_ModU128:
+ case Iop_ModS128:
+ /* I128 x I128 -> I128 */
++ complainIfOperandsUndefined(mce, atom1, atom2);
+ return mkLazy2(mce, Ity_V128, vatom1, vatom2);
+
+ case Iop_QNarrowBin64Sto32Sx4:
+@@ -4687,10 +4739,12 @@
+
+ case Iop_DivModU64to32:
+ case Iop_DivModS64to32:
++ complainIfOperandsUndefined(mce, atom1, atom2);
+ return mkLazy2(mce, Ity_I64, vatom1, vatom2);
+
+ case Iop_DivModU128to64:
+ case Iop_DivModS128to64:
++ complainIfOperandsUndefined(mce, atom1, atom2);
+ return mkLazy2(mce, Ity_I128, vatom1, vatom2);
+
+ case Iop_8HLto16:
+@@ -4703,6 +4757,7 @@
+ case Iop_DivModU64to64:
+ case Iop_DivModS64to64: {
+ IRAtom* vTmp64 = mkLazy2(mce, Ity_I64, vatom1, vatom2);
++ complainIfOperandsUndefined(mce, atom1, atom2);
+ return assignNew('V', mce, Ity_I128,
+ binop(Iop_64HLto128, vTmp64, vTmp64));
+ }
+@@ -4718,6 +4773,7 @@
+ case Iop_DivModU32to32:
+ case Iop_DivModS32to32: {
+ IRAtom* vTmp32 = mkLazy2(mce, Ity_I32, vatom1, vatom2);
++ complainIfOperandsUndefined(mce, atom1, atom2);
+ return assignNew('V', mce, Ity_I64,
+ binop(Iop_32HLto64, vTmp32, vTmp32));
+ }
+@@ -4745,11 +4801,14 @@
+ return assignNew('V', mce, Ity_I16, binop(Iop_8HLto16, vHi8, vLo8));
+ }
+
+- case Iop_Sad8Ux4: /* maybe we could do better? ftm, do mkLazy2. */
+ case Iop_DivS32:
+ case Iop_DivU32:
+ case Iop_DivU32E:
+ case Iop_DivS32E:
++ complainIfOperandsUndefined(mce, atom1, atom2);
++ return mkLazy2(mce, Ity_I32, vatom1, vatom2);
++
++ case Iop_Sad8Ux4: /* maybe we could do better? ftm, do mkLazy2. */
+ case Iop_QAdd32S: /* could probably do better */
+ case Iop_QSub32S: /* could probably do better */
+ return mkLazy2(mce, Ity_I32, vatom1, vatom2);
+@@ -4758,6 +4817,7 @@
+ case Iop_DivU64:
+ case Iop_DivS64E:
+ case Iop_DivU64E:
++ complainIfOperandsUndefined(mce, atom1, atom2);
+ return mkLazy2(mce, Ity_I64, vatom1, vatom2);
+
+ case Iop_Add32:
diff --git a/nix/probe.nix b/nix/probe.nix
@@ -0,0 +1,146 @@
+# The probe check: etc/probe/harness.c under both instruments, each
+# site and origin it should show found where it should be, and
+# nothing else in the harness. On an x86_64 host, the same harness
+# built for aarch64 is traced differentially too, under QEMU; memcheck
+# needs a native host.
+{ pkgs, vestigia }:
+
+let
+ lib = pkgs.lib;
+
+ # the harness, built by a package set's C compiler and linked at a
+ # fixed address, where an instruction's address in the file is not
+ # its offset there
+ probeOf = ps: ps.runCommandCC "vestigia-probe" {
+ hardeningDisable = [ "fortify" ];
+ } ''
+ mkdir -p $out/bin
+ $CC -O0 -g -fno-pie -no-pie -I${vestigia.include}/include \
+ -I${vestigia.valgrindDev}/include \
+ -o $out/bin/probe ${../etc/probe/harness.c} \
+ ${vestigia.include}/include/vestigia.c
+ $READELF -h $out/bin/probe | grep -q 'Type: *EXEC'
+ '';
+
+ probe = probeOf pkgs;
+ cross = probeOf pkgs.pkgsCross.aarch64-multiplatform;
+ x86_64 = pkgs.stdenv.hostPlatform.isx86_64;
+
+ threads = pkgs.runCommandCC "vestigia-probe-threads" { } ''
+ mkdir -p $out/bin
+ cc -O0 -pthread -o $out/bin/threads ${../etc/probe/threads.c}
+ '';
+
+ secrets = [ "00000005" "0000003a" "000000c3" ];
+ objects = [ "/bin/probe" ];
+
+ trace = vestigia.traceOf {
+ name = "probe";
+ harness = "${probe}/bin/probe";
+ runs = map (s: [ s ]) secrets;
+ inherit objects;
+ };
+
+ diffOf = name: harness: vestigia.diffOf {
+ inherit name objects;
+ harness = "${harness}/bin/probe";
+ runs = map (s: [ s ]) secrets;
+ };
+ diff = diffOf "probe" probe;
+ diffCross = diffOf "probe-aarch64" cross;
+
+ # each report's (class, function) pairs in the harness, sorted
+ expected = {
+ trace = [ [ "address" "lookup" ] [ "address" "rare" ]
+ [ "control" "branchy" ] [ "control" "calls" ]
+ [ "control" "rare" ] [ "operand" "divide" ]
+ [ "operand" "divide_memory" ] ];
+ diff = [ [ "address" "lookup" ] [ "control" "branchy" ]
+ [ "control" "calls" ] [ "control" "rare" ]
+ [ "operand" "divide" ] [ "operand" "divide_memory" ] ];
+ };
+in
+pkgs.runCommand "vestigia-probe-check" {
+ nativeBuildInputs = [ pkgs.jq ];
+} ''
+ check() {
+ got=$(jq -c "$2" "$1")
+ if [ "$got" != "$3" ]; then
+ echo "probe: $1: expected $3, got $got" >&2
+ exit 1
+ fi
+ }
+ check ${trace}/trace.json \
+ '[.sites[] | [.class, .function]] | unique' \
+ '${builtins.toJSON expected.trace}'
+ check ${diff}/diff.json \
+ '[.origins[] | [.class, .frames[0].function]] | unique' \
+ '${builtins.toJSON expected.diff}'
+
+ # every secret is traced under taint, and the table index on the
+ # third secret's path is that run's alone
+ check ${trace}/trace.json '[.runs[] | .exit]' '[0,0,0]'
+ check ${trace}/trace.json \
+ '[.sites[] | select(.function == "rare" and .class == "address")
+ | .runs]' \
+ '[["run-3"]]'
+
+ # both instruments name each instruction they both saw by one
+ # address: a division memcheck reports where it divides, not at the
+ # memory access before it
+ check ${trace}/trace.json \
+ '[.sites[] | select(.class == "operand") | .offset] | sort' \
+ "$(jq -c '[.origins[] | select(.class == "operand") | .offset]
+ | sort' ${diff}/diff.json)"
+ ${lib.optionalString x86_64 ''
+ check ${diffCross}/diff.json \
+ '[.origins[] | [.class, .frames[0].function]] | unique' \
+ '${builtins.toJSON expected.diff}'
+ ''}
+
+ # each origin's stack runs from its own function to the call in
+ # main that reached it
+ for d in ${diff} ${lib.optionalString x86_64 "${diffCross}"}; do
+ check $d/diff.json \
+ '[.origins[] | [.stacks[0][0].function, .stacks[0][1].function]
+ | .[1]] | unique' \
+ '["main"]'
+ done
+
+ # each run as it was made: the declared, then the control
+ check ${diff}/diff.json \
+ '[.runs[] | [.kind, .arguments[1], .status]]' \
+ '${builtins.toJSON (map (s: [ "declared" s 0 ]) secrets
+ ++ [ [ "control" (builtins.head secrets) 0 ] ])}'
+
+ v=${vestigia.vestigia}/bin/vestigia
+
+ # a control must repeat the run it controls, and every run must lay
+ # out as the first: its arguments of one number and length
+ $v record --dump a -- ${probe}/bin/probe 00000005
+ $v record --dump b -- ${probe}/bin/probe 0000003a
+ $v record --dump c -- ${probe}/bin/probe 000000003a
+ if $v diff --control b a a 2> refusal; then
+ echo "probe: a control repeating another secret was taken" >&2
+ exit 1
+ fi
+ grep -q 'does not repeat' refusal
+ if $v diff a c 2> refusal; then
+ echo "probe: a run with a longer argument was compared" >&2
+ exit 1
+ fi
+ grep -q 'number or length' refusal
+
+ # a guest that starts a second thread is stopped, and its dump
+ # refused
+ if $v record --dump threads -- ${threads}/bin/threads; then
+ echo "probe: a guest's second thread was recorded" >&2
+ exit 1
+ fi
+ if $v diff threads threads 2> refusal; then
+ echo "probe: a stopped guest's dump was compared" >&2
+ exit 1
+ fi
+ grep -q 'second thread' refusal
+ touch $out
+''
diff --git a/plugin/vestigia-qemu.c b/plugin/vestigia-qemu.c
@@ -18,53 +18,196 @@
* Nothing needs aligning, and no taint is propagated, so effects of
* control flow are seen as well as those of data flow.
*
+ * It reads each instruction's bytes, x86_64's or aarch64's, for three
+ * kinds. A return goes where the call before it sent it, and is
+ * marked. An integer division takes a time that depends on its
+ * operands, so it gets an order-sensitive fingerprint of their
+ * values: the dividend and a register divisor read before it runs,
+ * and a divisor in memory as it is loaded. A division run as often
+ * but on other operands computed them from the secret. And a call,
+ * with the returns, keeps a shadow stack of the calls in progress,
+ * so that an instruction that could be an origin (one ending a
+ * translation block, as every branch does, one touching memory, or a
+ * division) is given the contexts it ran in: the chains of calls, by
+ * their addresses, that reached it, up to CONTEXTS of them.
+ *
* At exit it writes, to the file named by its `out` argument:
*
- * I <pc> <count> <accesses> <fingerprint> <order> <object> <offset>
+ * I <pc> <count> <accesses> <fingerprint> <order> <object> <address>
* E <from> <to> <count>
+ * R <pc>
+ * D <pc> <operands>
+ * C <context> <caller> <call>
+ * K <pc> <partial> <context>...
*
* in hex, where <object> is the file the instruction's bytes were
- * mapped from ("-" if none) and <offset> its offset in that file.
+ * mapped from ("-" if none, or if the file's program headers cannot
+ * be read) and <address> its address in that file: where the file's
+ * program headers place it, as its disassembly and line tables name
+ * it. In a shared library that is often the instruction's offset in
+ * the file; in an executable linked at a fixed address it is not. A
+ * context is the call at <call> made in context <caller>, context 0
+ * being the program's own; <partial> is 1 where an instruction ran in
+ * more contexts than are kept. A guest that started a second thread
+ * gets the line `T 2` alone.
*
- * A single-threaded guest is assumed: the state below is unlocked.
+ * The state below is unlocked, so one guest thread is recorded: a
+ * guest that starts a second one is stopped there, its dump saying
+ * so, rather than recorded by threads racing on it.
*/
+#include <elf.h>
#include <glib.h>
#include <inttypes.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
+#include <unistd.h>
#include <qemu-plugin.h>
QEMU_PLUGIN_EXPORT int qemu_plugin_version = QEMU_PLUGIN_VERSION;
+/* what an instruction is to a comparison, read from its bytes */
+enum { PLAIN, RETURN, DIVISION, CALL };
+
+/* the most contexts kept for one instruction */
+#define CONTEXTS 16
+
+/* registers by number: x86_64's in ModRM order, aarch64's X0 to X30;
+ aarch64's 31 is the zero register where a division names it */
+enum { RAX = 0, RDX = 2, ZR = 31, GPRS = 32 };
+
+typedef struct Decoded {
+ int kind;
+ /* a division's: its width in bits; on aarch64 its two registers,
+ on x86_64 its divisor's (-1 in memory), that register's second
+ byte where `high`, the dividend being RDX:RAX or AX */
+ int width, a, b, high;
+} Decoded;
+
typedef struct Insn {
uint64_t pc;
uint64_t size;
uintptr_t haddr;
+ Decoded d;
uint64_t count;
uint64_t accesses;
uint64_t fingerprint;
uint64_t order; /* the successors, in the order they followed */
+ uint64_t operands; /* a division's operands, in order */
GHashTable *succ; /* target pc -> count, for transfers */
+ uint32_t last; /* the context it last ran in */
+ uint32_t contexts[CONTEXTS];
+ int ncontexts, partial;
+ int origin; /* it ends a block or divides: it could be one */
+ /* a call's: the context it was last made in, and the one it made */
+ uint32_t made_in, made;
} Insn;
+/* a context: the context a call was made in, and the call */
+typedef struct Context {
+ uint32_t caller;
+ uint64_t call;
+} Context;
+
+/* a call in progress: where it returns, and the context it left */
+typedef struct Call {
+ uint64_t ret;
+ uint32_t left;
+} Call;
+
static GHashTable *insns; /* pc -> Insn */
static Insn *prev; /* the instruction executed last */
static char *out_path;
+static gint vcpus; /* the guest's threads, a vCPU each */
+static gboolean aarch64; /* the guest's ISA: aarch64, else x86_64 */
+static GArray *contexts; /* Context by number, 0 the program's own */
+static GHashTable *interned; /* Context -> its number */
+static GArray *calls; /* the calls in progress, innermost last */
+static uint32_t current; /* the context the guest runs in */
+static struct qemu_plugin_register *gpr[GPRS];
+static GByteArray *regbuf;
static const uint64_t fnv_offset = 0xcbf29ce484222325ULL;
static const uint64_t fnv_prime = 0x100000001b3ULL;
-static Insn *insn_at(uint64_t pc, uint64_t size, uintptr_t haddr) {
+static Decoded decode_aarch64(const uint8_t *b, size_t n) {
+ Decoded d = { PLAIN, 0, 0, 0, 0 };
+ uint32_t w;
+ if (n < 4) return d;
+ w = (uint32_t)b[0] | (uint32_t)b[1] << 8 | (uint32_t)b[2] << 16
+ | (uint32_t)b[3] << 24;
+ /* RET Xn, RETAA, RETAB */
+ if ((w & 0xfffffc1f) == 0xd65f0000 || w == 0xd65f0bff
+ || w == 0xd65f0fff)
+ d.kind = RETURN;
+ /* BL, BLR, BLRAAZ, BLRABZ, BLRAA, BLRAB */
+ else if ((w & 0xfc000000) == 0x94000000
+ || (w & 0xfffffc1f) == 0xd63f0000
+ || (w & 0xfffff81f) == 0xd63f081f
+ || (w & 0xfffff800) == 0xd73f0800)
+ d.kind = CALL;
+ /* UDIV, SDIV */
+ else if ((w & 0x7fe0f800) == 0x1ac00800) {
+ d.kind = DIVISION;
+ d.width = (w >> 31) ? 64 : 32;
+ d.a = (int)((w >> 5) & 31);
+ d.b = (int)((w >> 16) & 31);
+ }
+ return d;
+}
+
+static Decoded decode_x86_64(const uint8_t *b, size_t n) {
+ Decoded d = { PLAIN, 0, 0, 0, 0 };
+ size_t k = 0;
+ int opsize = 0, rex = 0;
+ /* past the legacy prefixes, then a REX */
+ while (k < n && (b[k] == 0x66 || b[k] == 0x67 || b[k] == 0xf0
+ || b[k] == 0xf2 || b[k] == 0xf3 || b[k] == 0x2e
+ || b[k] == 0x36 || b[k] == 0x3e || b[k] == 0x26
+ || b[k] == 0x64 || b[k] == 0x65)) {
+ if (b[k] == 0x66) opsize = 1;
+ k++;
+ }
+ if (k < n && (b[k] & 0xf0) == 0x40) rex = b[k++];
+ if (k >= n) return d;
+ /* RET, RET imm16 */
+ if (b[k] == 0xc3 || b[k] == 0xc2) d.kind = RETURN;
+ /* CALL rel32, CALL r/m: FF with ModRM's reg 2 */
+ else if (b[k] == 0xe8
+ || (b[k] == 0xff && k + 1 < n && ((b[k + 1] >> 3) & 7) == 2))
+ d.kind = CALL;
+ /* DIV, IDIV: F6 or F7 with ModRM's reg 6 or 7 */
+ else if ((b[k] == 0xf6 || b[k] == 0xf7) && k + 1 < n
+ && ((b[k + 1] >> 3) & 6) == 6) {
+ int modrm = b[k + 1], rm = modrm & 7;
+ d.kind = DIVISION;
+ d.width = b[k] == 0xf6 ? 8 : (rex & 8) ? 64 : opsize ? 16 : 32;
+ if ((modrm >> 6) != 3) d.a = -1;
+ /* without REX, a byte register 4 to 7 is AH, CH, DH, or BH */
+ else if (d.width == 8 && rex == 0 && rm >= 4) {
+ d.a = rm - 4;
+ d.high = 1;
+ } else
+ d.a = rm | ((rex & 1) << 3);
+ }
+ return d;
+}
+
+static Insn *insn_at(uint64_t pc, uint64_t size, uintptr_t haddr,
+ Decoded d) {
Insn *i = g_hash_table_lookup(insns, &pc);
if (i == NULL) {
i = g_new0(Insn, 1);
i->pc = pc;
i->size = size;
i->haddr = haddr;
+ i->d = d;
i->fingerprint = fnv_offset;
i->order = fnv_offset;
+ i->operands = fnv_offset;
+ i->last = UINT32_MAX;
+ i->made_in = UINT32_MAX;
i->succ = g_hash_table_new_full(g_int64_hash, g_int64_equal,
g_free, g_free);
g_hash_table_insert(insns, &i->pc, i);
@@ -83,24 +226,178 @@ static void transfer(Insn *from, uint64_t to) {
(*n)++;
}
+static guint context_hash(gconstpointer p) {
+ const Context *c = p;
+ return (guint)((c->call * 0x9e3779b97f4a7c15ULL) >> 32) ^ c->caller;
+}
+
+static gboolean context_equal(gconstpointer a, gconstpointer b) {
+ const Context *x = a, *y = b;
+ return x->caller == y->caller && x->call == y->call;
+}
+
+static uint32_t context_of(uint32_t caller, uint64_t call) {
+ Context c = { caller, call };
+ gpointer v;
+ if (g_hash_table_lookup_extended(interned, &c, NULL, &v))
+ return GPOINTER_TO_UINT(v);
+ uint32_t n = contexts->len;
+ g_array_append_val(contexts, c);
+ g_hash_table_insert(interned, g_memdup2(&c, sizeof c),
+ GUINT_TO_POINTER(n));
+ return n;
+}
+
+/* a call made: it returns past itself */
+static void enter(Insn *call) {
+ Call c = { call->pc + call->size, current };
+ g_array_append_val(calls, c);
+ if (call->made_in != current) {
+ call->made_in = current;
+ call->made = context_of(current, call->pc);
+ }
+ current = call->made;
+}
+
+/* a return made, to pc: the innermost call returning there ends, and
+ any inside it that never returned; a return no call made leaves
+ the stack as it is */
+static void leave(uint64_t pc) {
+ for (guint k = calls->len; k > 0; k--) {
+ const Call *c = &g_array_index(calls, Call, k - 1);
+ if (c->ret == pc) {
+ current = c->left;
+ g_array_set_size(calls, k - 1);
+ return;
+ }
+ }
+}
+
+static void note_context(Insn *i) {
+ i->last = current;
+ /* once more have been seen than are kept, no more is learnt */
+ if (i->partial) return;
+ for (int k = 0; k < i->ncontexts; k++)
+ if (i->contexts[k] == current) return;
+ if (i->ncontexts < CONTEXTS)
+ i->contexts[i->ncontexts++] = current;
+ else
+ i->partial = 1;
+}
+
static void on_exec(unsigned int vcpu, void *udata) {
Insn *i = udata;
(void)vcpu;
if (prev != NULL) {
prev->order = (prev->order ^ i->pc) * fnv_prime;
if (i->pc != prev->pc + prev->size) transfer(prev, i->pc);
+ if (prev->d.kind == CALL) enter(prev);
+ else if (prev->d.kind == RETURN) leave(i->pc);
}
prev = i;
i->count++;
+ if (i->origin && i->last != current) note_context(i);
+}
+
+static void mix(Insn *i, uint64_t v) {
+ i->operands = (i->operands ^ v) * fnv_prime;
+}
+
+static uint64_t read_gpr(int r) {
+ uint64_t v = 0;
+ int n;
+ if (aarch64 && r == ZR) return 0;
+ g_byte_array_set_size(regbuf, 0);
+ n = qemu_plugin_read_register(gpr[r], regbuf);
+ /* in the guest's byte order, little-endian as the host's */
+ if (n > 0) memcpy(&v, regbuf->data, MIN((size_t)n, sizeof v));
+ return v;
+}
+
+static void on_divide(unsigned int vcpu, void *udata) {
+ Insn *i = udata;
+ uint64_t mask = i->d.width == 64 ? ~0ULL : (1ULL << i->d.width) - 1;
+ (void)vcpu;
+ if (aarch64) {
+ mix(i, read_gpr(i->d.a) & mask);
+ mix(i, read_gpr(i->d.b) & mask);
+ return;
+ }
+ if (i->d.width == 8)
+ mix(i, read_gpr(RAX) & 0xffff);
+ else {
+ mix(i, read_gpr(RAX) & mask);
+ mix(i, read_gpr(RDX) & mask);
+ }
+ /* a divisor in memory is mixed in as it is loaded */
+ if (i->d.a >= 0)
+ mix(i, (read_gpr(i->d.a) >> (i->d.high ? 8 : 0)) & mask);
}
static void on_mem(unsigned int vcpu, qemu_plugin_meminfo_t info,
uint64_t vaddr, void *udata) {
Insn *i = udata;
(void)vcpu;
- (void)info;
i->fingerprint = (i->fingerprint ^ vaddr) * fnv_prime;
i->accesses++;
+ if (i->last != current) note_context(i);
+ if (i->d.kind == DIVISION) {
+ qemu_plugin_mem_value v = qemu_plugin_mem_get_value(info);
+ switch (v.type) {
+ case QEMU_PLUGIN_MEM_VALUE_U8: mix(i, v.data.u8); break;
+ case QEMU_PLUGIN_MEM_VALUE_U16: mix(i, v.data.u16); break;
+ case QEMU_PLUGIN_MEM_VALUE_U32: mix(i, v.data.u32); break;
+ case QEMU_PLUGIN_MEM_VALUE_U64: mix(i, v.data.u64); break;
+ case QEMU_PLUGIN_MEM_VALUE_U128:
+ mix(i, v.data.u128.low);
+ mix(i, v.data.u128.high);
+ break;
+ }
+ }
+}
+
+/* the general registers a division reads, by the names QEMU's
+ debugger stub gives them */
+static void find_registers(void) {
+ static const char *x86_64[16] = {
+ "rax", "rcx", "rdx", "rbx", "rsp", "rbp", "rsi", "rdi",
+ "r8", "r9", "r10", "r11", "r12", "r13", "r14", "r15" };
+ GArray *rs = qemu_plugin_get_registers();
+ int wanted = aarch64 ? 31 : 16;
+ for (guint k = 0; k < rs->len; k++) {
+ qemu_plugin_reg_descriptor *r =
+ &g_array_index(rs, qemu_plugin_reg_descriptor, k);
+ for (int j = 0; j < wanted; j++) {
+ char name[8];
+ if (aarch64) g_snprintf(name, sizeof name, "x%d", j);
+ if (strcmp(r->name, aarch64 ? name : x86_64[j]) == 0)
+ gpr[j] = r->handle;
+ }
+ }
+ g_array_free(rs, TRUE);
+ for (int j = 0; j < wanted; j++)
+ if (gpr[j] == NULL) {
+ fprintf(stderr, "vestigia-qemu: QEMU names no register %d, by "
+ "which a division's operands are read\n", j);
+ _exit(EXIT_FAILURE);
+ }
+}
+
+static void on_vcpu_init(qemu_plugin_id_t id, unsigned int vcpu) {
+ (void)id;
+ (void)vcpu;
+ if (g_atomic_int_add(&vcpus, 1) == 0)
+ find_registers();
+ else {
+ FILE *out = fopen(out_path, "w");
+ if (out != NULL) {
+ fprintf(out, "T 2\n");
+ fclose(out);
+ }
+ fprintf(stderr, "vestigia-qemu: the guest started a second thread, "
+ "which a trace cannot record; the run is stopped\n");
+ _exit(EXIT_FAILURE);
+ }
}
static void on_translate(qemu_plugin_id_t id, struct qemu_plugin_tb *tb) {
@@ -108,11 +405,19 @@ static void on_translate(qemu_plugin_id_t id, struct qemu_plugin_tb *tb) {
(void)id;
for (size_t k = 0; k < n; k++) {
struct qemu_plugin_insn *qi = qemu_plugin_tb_get_insn(tb, k);
+ uint8_t bytes[16];
+ size_t len = qemu_plugin_insn_data(qi, bytes, sizeof bytes);
Insn *i = insn_at(qemu_plugin_insn_vaddr(qi),
qemu_plugin_insn_size(qi),
- (uintptr_t)qemu_plugin_insn_haddr(qi));
+ (uintptr_t)qemu_plugin_insn_haddr(qi),
+ aarch64 ? decode_aarch64(bytes, len)
+ : decode_x86_64(bytes, len));
+ if (k == n - 1 || i->d.kind == DIVISION) i->origin = 1;
qemu_plugin_register_vcpu_insn_exec_cb(qi, on_exec,
QEMU_PLUGIN_CB_NO_REGS, i);
+ if (i->d.kind == DIVISION)
+ qemu_plugin_register_vcpu_insn_exec_cb(qi, on_divide,
+ QEMU_PLUGIN_CB_R_REGS, i);
qemu_plugin_register_vcpu_mem_cb(qi, on_mem, QEMU_PLUGIN_CB_NO_REGS,
QEMU_PLUGIN_MEM_RW, i);
}
@@ -158,6 +463,70 @@ static const Region *region_of(GArray *rs, uintptr_t a) {
return NULL;
}
+/* a file's loadable segments, by which a file offset is placed at
+ the address the file's own disassembly gives it */
+typedef struct Segments {
+ guint n;
+ Elf64_Phdr *load;
+} Segments;
+
+static Segments *read_segments(const char *path) {
+ FILE *f = fopen(path, "rb");
+ Elf64_Ehdr eh;
+ Segments *s = NULL;
+ if (f == NULL) return NULL;
+ /* a little-endian ELF64 object, as x86_64 and aarch64 build */
+ if (fread(&eh, sizeof eh, 1, f) != 1
+ || memcmp(eh.e_ident, ELFMAG, SELFMAG) != 0
+ || eh.e_ident[EI_CLASS] != ELFCLASS64
+ || eh.e_ident[EI_DATA] != ELFDATA2LSB
+ || eh.e_phentsize != sizeof(Elf64_Phdr)
+ || fseek(f, (long)eh.e_phoff, SEEK_SET) != 0) {
+ fclose(f);
+ return NULL;
+ }
+ s = g_new0(Segments, 1);
+ s->load = g_new0(Elf64_Phdr, eh.e_phnum);
+ for (guint k = 0; k < eh.e_phnum; k++) {
+ Elf64_Phdr ph;
+ if (fread(&ph, sizeof ph, 1, f) != 1) {
+ g_free(s->load);
+ g_free(s);
+ fclose(f);
+ return NULL;
+ }
+ if (ph.p_type == PT_LOAD) s->load[s->n++] = ph;
+ }
+ fclose(f);
+ return s;
+}
+
+/* the segments of the file at a path, read once; NULL if they cannot
+ be read, which is said once */
+static Segments *segments_of(GHashTable *cache, const char *path) {
+ gpointer v;
+ if (g_hash_table_lookup_extended(cache, path, NULL, &v)) return v;
+ Segments *s = read_segments(path);
+ if (s == NULL)
+ fprintf(stderr, "vestigia-qemu: cannot read the program headers "
+ "of %s; its instructions are named by no object\n", path);
+ g_hash_table_insert(cache, g_strdup(path), s);
+ return s;
+}
+
+/* where a file's segments place the byte at a file offset */
+static gboolean address_in(const Segments *s, uint64_t off,
+ uint64_t *addr) {
+ for (guint k = 0; k < s->n; k++) {
+ const Elf64_Phdr *p = &s->load[k];
+ if (off >= p->p_offset && off - p->p_offset < p->p_filesz) {
+ *addr = p->p_vaddr + (off - p->p_offset);
+ return TRUE;
+ }
+ }
+ return FALSE;
+}
+
static void at_exit(qemu_plugin_id_t id, void *p) {
(void)id;
(void)p;
@@ -167,21 +536,34 @@ static void at_exit(qemu_plugin_id_t id, void *p) {
return;
}
GArray *rs = read_maps();
+ GHashTable *segs = g_hash_table_new(g_str_hash, g_str_equal);
GHashTableIter it;
gpointer key, val;
g_hash_table_iter_init(&it, insns);
while (g_hash_table_iter_next(&it, &key, &val)) {
Insn *i = val;
const Region *r = region_of(rs, i->haddr);
- if (r != NULL)
+ Segments *s = r != NULL ? segments_of(segs, r->path) : NULL;
+ uint64_t addr;
+ if (s != NULL
+ && address_in(s, (uint64_t)(i->haddr - r->start) + r->offset,
+ &addr))
fprintf(out, "I %" PRIx64 " %" PRIx64 " %" PRIx64 " %016" PRIx64
" %016" PRIx64 " %s %" PRIx64 "\n", i->pc, i->count,
- i->accesses, i->fingerprint, i->order, r->path,
- (uint64_t)(i->haddr - r->start) + r->offset);
+ i->accesses, i->fingerprint, i->order, r->path, addr);
else
fprintf(out, "I %" PRIx64 " %" PRIx64 " %" PRIx64 " %016" PRIx64
" %016" PRIx64 " - 0\n", i->pc, i->count, i->accesses,
i->fingerprint, i->order);
+ if (i->d.kind == RETURN) fprintf(out, "R %" PRIx64 "\n", i->pc);
+ if (i->d.kind == DIVISION)
+ fprintf(out, "D %" PRIx64 " %016" PRIx64 "\n", i->pc, i->operands);
+ if (i->ncontexts > 0) {
+ fprintf(out, "K %" PRIx64 " %d", i->pc, i->partial);
+ for (int k = 0; k < i->ncontexts; k++)
+ fprintf(out, " %" PRIx32, i->contexts[k]);
+ fprintf(out, "\n");
+ }
GHashTableIter jt;
gpointer tk, tn;
g_hash_table_iter_init(&jt, i->succ);
@@ -189,13 +571,18 @@ static void at_exit(qemu_plugin_id_t id, void *p) {
fprintf(out, "E %" PRIx64 " %" PRIx64 " %" PRIx64 "\n", i->pc,
*(uint64_t *)tk, *(uint64_t *)tn);
}
+ for (guint k = 1; k < contexts->len; k++) {
+ const Context *c = &g_array_index(contexts, Context, k);
+ fprintf(out, "C %x %" PRIx32 " %" PRIx64 "\n", k, c->caller,
+ c->call);
+ }
fclose(out);
}
QEMU_PLUGIN_EXPORT int qemu_plugin_install(qemu_plugin_id_t id,
const qemu_info_t *info,
int argc, char **argv) {
- (void)info;
+ aarch64 = strcmp(info->target_name, "aarch64") == 0;
for (int k = 0; k < argc; k++)
if (strncmp(argv[k], "out=", 4) == 0)
out_path = g_strdup(argv[k] + 4);
@@ -204,6 +591,16 @@ QEMU_PLUGIN_EXPORT int qemu_plugin_install(qemu_plugin_id_t id,
return -1;
}
insns = g_hash_table_new(g_int64_hash, g_int64_equal);
+ regbuf = g_byte_array_new();
+ contexts = g_array_new(FALSE, FALSE, sizeof(Context));
+ interned = g_hash_table_new_full(context_hash, context_equal, g_free,
+ NULL);
+ calls = g_array_new(FALSE, FALSE, sizeof(Call));
+ {
+ Context own = { 0, 0 };
+ g_array_append_val(contexts, own);
+ }
+ qemu_plugin_register_vcpu_init_cb(id, on_vcpu_init);
qemu_plugin_register_vcpu_tb_trans_cb(id, on_translate);
qemu_plugin_register_atexit_cb(id, at_exit, NULL);
return 0;
diff --git a/test/Main.hs b/test/Main.hs
@@ -79,21 +79,19 @@ memcheckTests = testGroup "memcheck"
traceTests :: TestTree
traceTests = testGroup "trace"
[ testCase "the probe's secret addresses are its sites" $ do
- tr <- trace <$> fixture "probe.xml"
- fmap (\s -> (siClass s, frFn (siFrame s), frLine (siFrame s)))
- (trSites tr)
+ tr <- one <$> fixture "probe.xml"
+ fmap (\s -> (siClass s, frFn (at s), frLine (at s))) (trSites tr)
@?= [ (Address, Just "lookup", Just 16)
, (Address, Just "main", Just 33) ]
trUnrelated tr @?= []
trFaults tr @?= []
, testCase "only a secret's descendants are sites" $ do
- tr <- trace <$> either assertFailure pure (readMemcheck mixed)
- fmap (\s -> (siClass s, frIp (siFrame s), siCount s))
- (trSites tr)
+ tr <- one <$> either assertFailure pure (readMemcheck mixed)
+ fmap (\s -> (siClass s, frIp (at s), siCount s)) (trSites tr)
@?= [ (Control, 0x10, 5) ]
- fmap meKind (trUnrelated tr) @?= [ "UninitValue" ]
- fmap meKind (trFaults tr) @?= [ "InvalidRead" ]
+ fmap (meKind . snd) (trUnrelated tr) @?= [ "UninitValue" ]
+ fmap (meKind . snd) (trFaults tr) @?= [ "InvalidRead" ]
, testCase "a frame is named by its address in its object" $ do
os <- either assertFailure pure
@@ -109,16 +107,39 @@ traceTests = testGroup "trace"
objectOffset os (f "/lib/libc.so.6" 0x7000) @?= Nothing
, testCase "a site is kept to the objects named" $ do
- tr <- trace <$> fixture "probe.xml"
+ tr <- one <$> fixture "probe.xml"
length (trSites (sitesIn [ "probe" ] tr)) @?= 2
trSites (sitesIn [ "libc" ] tr) @?= []
length (trSites (sitesIn [] tr)) @?= 2
, testCase "one site per instruction, whatever called it" $ do
- tr <- trace <$> either assertFailure pure (readMemcheck twoCallers)
- fmap (\s -> (frIp (siFrame s), siCount s, length (siStacks s)))
+ tr <- one <$> either assertFailure pure (readMemcheck twoCallers)
+ fmap (\s -> (frIp (at s), siCount s, length (siStacks s)))
(trSites tr)
@?= [ (0x10, 7, 2) ]
+
+ , testCase "runs' sites are one per instruction, with their runs" $ do
+ a <- either assertFailure pure (readMemcheck mixed)
+ b <- either assertFailure pure (readMemcheck twoCallers)
+ -- the same object loaded 0x100 higher in the second run: its
+ -- branch at 0x110 is the first run's at 0x10
+ let obj = "/lib.so"
+ inObj mc = mc { mcErrors =
+ [ e { meStack = [ f { frObj = Just obj }
+ | f <- meStack e ] }
+ | e <- mcErrors mc ] }
+ moved mc = mc { mcErrors =
+ [ e { meStack = [ f { frIp = frIp f + 0x100 }
+ | f <- meStack e ] }
+ | e <- mcErrors mc ] }
+ tr = trace
+ [ Taint "a" (inObj a) [ (0, obj) ] (Just 0)
+ , Taint "b" (moved (inObj b)) [ (0x100, obj) ] (Just 1) ]
+ fmap (\s -> (siClass s, lcOffset (siAt s), siCount s, siRuns s
+ , length (siStacks s)))
+ (trSites tr)
+ @?= [ (Control, Just 0x10, 5 + 7, [ 0, 1 ], 1 + 2) ]
+ fmap fst (trUnrelated tr) @?= [ 0 ]
]
diffTests :: TestTree
@@ -245,6 +266,63 @@ diffTests = testGroup "diff"
-- in the same order, nothing
dvOrigins (diffDumps [ a, a ]) @?= []
+ , testCase "a return goes where its call sent it: downstream" $ do
+ -- 0x50 returns four times in each run, to 0x30 twice in A and
+ -- three times in B, as the branch at 0x10 sent it
+ a <- either assertFailure pure (readDump (dumpA <> T.unlines
+ [ "I 50 4 0 aaaa 0 /lib.so 50", "R 50", "E 50 30 2"
+ , "E 50 60 2" ]))
+ b <- either assertFailure pure (readDump (dumpB <> T.unlines
+ [ "I 50 4 0 aaaa 0 /lib.so 50", "R 50", "E 50 30 3"
+ , "E 50 60 1" ]))
+ let dv = diffDumps [ a, b ]
+ fmap (\(o, i) -> (o, inPc i)) (dvOrigins dv)
+ @?= [ (ControlOrigin, 0x10), (AddressOrigin, 0x20) ]
+ fmap inPc (dvDownstream dv) @?= [ 0x30, 0x50 ]
+
+ , testCase "a division on other operands is an operand origin" $ do
+ -- 0x40 divides once in every run, on other operands in B; in a
+ -- designed run, on others again
+ a <- either assertFailure pure (readDump (dumpA <> "D 40 1111\n"))
+ b <- either assertFailure pure (readDump (dumpB <> "D 40 2222\n"))
+ x <- either assertFailure pure (readDump (dumpA <> "D 40 3333\n"))
+ let dv = diffDumps [ a, b ]
+ fmap (\(o, i) -> (o, inPc i)) (dvOrigins dv)
+ @?= [ (ControlOrigin, 0x10), (AddressOrigin, 0x20)
+ , (OperandOrigin, 0x40) ]
+ M.lookup (OperandOrigin, 0x40) (dvBehaviour (diffDumps [ a, b, a ]))
+ @?= Just ([ [ 0, 2 ], [ 1 ] ], [])
+ notElem 0x40 (fmap inPc (dvDownstream dv)) @? "downstream"
+ -- a designed run's operands say nothing of the secret
+ fmap (\(o, i) -> (o, inPc i)) (dvOrigins (diffDesigned [] [ a, a ]
+ [ x ])) @?= []
+ -- a control dividing other operands sets it apart as unsteady
+ fmap inPc (dvUnsteady (diffControlled [ x ] [ a, b ])) @?= [ 0x40 ]
+
+ , testCase "an origin is given the calls that reached it" $ do
+ -- 0x10 ran in context 2 (the call at 0x40 made in context 1,
+ -- the call at 0x30 made in the program's own) in A, and in the
+ -- program's own context too in B
+ let calls = T.unlines
+ [ "C 1 0 30", "C 2 1 40" ]
+ a <- either assertFailure pure (readDump (dumpA <> calls
+ <> "K 10 0 2\n"))
+ b <- either assertFailure pure (readDump (dumpB <> calls
+ <> "K 10 1 2 0\n"))
+ callsOf a 2 @?= [ (Just "/lib.so", 0x40), (Just "/lib.so", 0x30) ]
+ callsOf a 0 @?= []
+ M.lookup 0x10 (dvCallers (diffDumps [ a, b ]))
+ @?= Just ([ [ (Just "/lib.so", 0x40), (Just "/lib.so", 0x30) ]
+ , [] ], True)
+ M.lookup 0x10 (dvCallers (diffDumps [ a, a ]))
+ @?= Nothing
+
+ , testCase "contexts that do not chain back are refused" $ do
+ isLeft (readDump (dumpA <> "C 1 2 30\nC 2 1 40\n"))
+ @? "a context made in a later one"
+ isLeft (readDump (dumpA <> "K 10 0 5\n"))
+ @? "a context never made"
+
, testCase "identical runs have no origins" $ do
a <- either assertFailure pure (readDump dumpA)
let dv = diffDumps [ a, a ]
@@ -270,6 +348,34 @@ diffTests = testGroup "diff"
, testCase "an unreadable line is refused" $
isLeft (readDump "I 10 zz 0 f 0 /lib.so 0\n") @? "accepted"
+
+ , testCase "a guest stopped for a second thread is refused" $
+ isLeft (readDump "T 2\n") @? "accepted"
+
+ , testCase "a run's record reads whole" $ do
+ d <- either assertFailure pure (readDump (dumpA <> T.unlines
+ [ "A 2f62696e2f70", "A", "A 3035", "N 2 1a", "X -9" ]))
+ dpRun d @?= Just (Run [ "/bin/p", "", "05" ] (2, 0x1a) (-9))
+ fmap dpRun (readDump dumpA) @?= Right Nothing
+
+ , testCase "an incomplete record is refused" $ do
+ isLeft (readDump (dumpA <> "A 3035\nN 2 1a\n")) @? "no status"
+ isLeft (readDump (dumpA <> "N 2 1a\nX 0\n")) @? "no arguments"
+ isLeft (readDump (dumpA <> "A 305\nN 2 1a\nX 0\n"))
+ @? "half a byte"
+
+ , testCase "runs made apart are told apart" $ do
+ let r = Run [ "/bin/p", "05" ] (2, 0x1a) 0
+ runApart r r { rnArguments = [ "/bin/p", "3a" ], rnStatus = 1 }
+ @?= Nothing
+ isJust (runApart r r { rnArguments = [ "/bin/q", "05" ] })
+ @? "another program"
+ isJust (runApart r r { rnArguments = [ "/bin/p", "005" ] })
+ @? "a longer argument"
+ isJust (runApart r r { rnArguments = [ "/bin/p", "05", "x" ] })
+ @? "another argument"
+ isJust (runApart r r { rnEnvironment = (2, 0x1b) })
+ @? "a larger environment"
]
where
-- 0x10 is a branch run four times, taken twice in A and three
@@ -304,6 +410,19 @@ symbolTests = testGroup "symbol"
@?= [ (0x1234, [ Place (Just "inner") (Just "/src/a.rs") (Just 12)
, Place (Just "outer") (Just "/src/b.rs") (Just 40) ])
, (0x5678, [ Place Nothing Nothing Nothing ]) ]
+
+ , testCase "a legacy Rust name's escapes and hash undone" $ do
+ rustLegacy "decaf377::ark_curve::encoding::_$LT$impl$u20$decaf377\
+ \..ark_curve..element..projective..Element$GT$::vartime\
+ \_compress_to_field::h346fee1681a4f34f"
+ @?= "decaf377::ark_curve::encoding::<impl decaf377::ark_curve::\
+ \element::projective::Element>::vartime_compress_to_field"
+ rustLegacy "_$LT$$RF$T$u20$as$u20$core..fmt..Debug$GT$::fmt::\
+ \h0123456789abcdef"
+ @?= "<&T as core::fmt::Debug>::fmt"
+ -- a C++ name, or one without a hash, is left as it is
+ rustLegacy "std::vector<int>::size" @?= "std::vector<int>::size"
+ rustLegacy "a::b$LT$c" @?= "a::b$LT$c"
]
jsonTests :: TestTree
@@ -314,6 +433,14 @@ jsonTests = testGroup "json"
@?= "{\n \"b\": 1,\n \"a\": \"q\\\"\\n\\u0001\"\n}\n"
]
+-- a trace of one run, of which memcheck's report is all that is
+-- known
+one :: Memcheck -> Trace
+one mc = trace [ Taint "run" mc [] Nothing ]
+
+at :: Site -> Frame
+at = lcFrame . siAt
+
fixture :: FilePath -> IO Memcheck
fixture f = do
b <- BS.readFile ("test/fixtures/" <> f)
@@ -324,6 +451,11 @@ isLeft e = case e of
Left _ -> True
Right _ -> False
+isJust :: Maybe a -> Bool
+isJust m = case m of
+ Just _ -> True
+ Nothing -> False
+
-- a secret branch, an uninitialised heap read, a bad read, and a
-- leak report
mixed :: T.Text
diff --git a/vestigia.cabal b/vestigia.cabal
@@ -38,6 +38,7 @@ library
, Vestigia.Xml
build-depends:
base >= 4.9 && < 5
+ , bytestring
, containers
, process
, text
@@ -55,6 +56,7 @@ executable vestigia
build-depends:
base
, bytestring
+ , containers
, directory
, filepath
, process
