deterministic-executor

Deterministic Executor

Reproducible and Auditable Execution

A comprehensive framework ensuring deterministic execution for reproducibility and auditability. Provides mechanisms to capture, replay, and verify execution traces with cryptographic guarantees, enabling reproducible builds, forensic analysis, and compliance verification.

Overview

deterministic-executor enables reproducible execution by controlling sources of non-determinism in programs. It captures complete execution traces, supports deterministic replay, and provides cryptographic verification of execution correctness.

Features

Core Capabilities

• Deterministic Execution: Control all sources of non-determinism
• Execution Recording: Capture complete execution traces
• Deterministic Replay: Reproduce exact execution behavior
• Cryptographic Verification: Tamper-proof execution logs
• Time Virtualization: Deterministic time and timestamps
• Entropy Control: Deterministic random number generation
• Input/Output Recording: Capture all I/O operations

Advanced Features

• Multi-Process Support: Deterministic execution of process trees
• Network Replay: Record and replay network interactions
• File System Snapshots: Capture filesystem state
• Signal Determinism: Deterministic signal delivery
• Thread Scheduling: Deterministic multi-threaded execution
• System Call Recording: Complete syscall trace logs
• Merkle Trees: Cryptographic execution attestation

Use Cases

• Reproducible Builds: Ensure bit-for-bit identical builds
• Forensic Analysis: Analyze security incidents
• Compliance Auditing: Prove correct execution
• Testing & Debugging: Reproduce race conditions
• Scientific Computing: Reproducible experiments
• Blockchain Execution: Deterministic smart contracts

Architecture

┌─────────────────────────────────────────────┐
│         Application Layer                   │
│  (Application under deterministic execution)│
└─────────────────┬───────────────────────────┘
                  │
┌─────────────────▼───────────────────────────┐
│     Determinism Control Layer               │
│  - Time Virtualization                      │
│  - Entropy Management                       │
│  - Signal Control                           │
│  - Thread Scheduler                         │
└─────────────────┬───────────────────────────┘
                  │
┌─────────────────▼───────────────────────────┐
│     Recording & Replay Engine               │
│  - Syscall Interceptor                      │
│  - I/O Recorder                             │
│  - State Snapshotter                        │
│  - Replay Controller                        │
└─────────────────┬───────────────────────────┘
                  │
┌─────────────────▼───────────────────────────┐
│     Cryptographic Verification              │
│  - Hash Chain                               │
│  - Merkle Tree                              │
│  - Signature Generation                     │
│  - Attestation                              │
└─────────────────────────────────────────────┘

Installation

As a Git Submodule

git submodule add https://github.com/navinBRuas/_SecureExecutionEnvironment.git vendor/secure-execution
cd vendor/secure-execution/deterministic-executor
make

As a System Library

make install PREFIX=/usr/local

Quick Start

Basic Deterministic Execution (C)

#include <deterministic-executor/detexec.h>

int main() {
    // Create deterministic execution context
    detexec_context_t *ctx = detexec_new();
    
    // Configure determinism
    detexec_config_t config = {
        .deterministic_time = true,
        .deterministic_entropy = true,
        .record_execution = true,
        .output_path = "execution.trace"
    };
    
    detexec_set_config(ctx, &config);
    
    // Execute program deterministically
    const char *argv[] = {"/usr/bin/myapp", "--option", NULL};
    detexec_result_t result;
    
    if (detexec_exec(ctx, "/usr/bin/myapp", argv, &result) != 0) {
        fprintf(stderr, "Execution failed\n");
        return 1;
    }
    
    printf("Execution completed: exit=%d\n", result.exit_code);
    printf("Trace saved to: %s\n", config.output_path);
    printf("Trace hash: %s\n", result.trace_hash);
    
    detexec_free(ctx);
    return 0;
}

Replaying Execution

#include <deterministic-executor/detexec.h>

int main() {
    // Create replay context
    detexec_context_t *ctx = detexec_new();
    
    // Load execution trace
    detexec_trace_t *trace = detexec_load_trace("execution.trace");
    if (!trace) {
        fprintf(stderr, "Failed to load trace\n");
        return 1;
    }
    
    // Verify trace integrity
    if (!detexec_verify_trace(trace)) {
        fprintf(stderr, "Trace verification failed\n");
        return 1;
    }
    
    // Replay execution
    detexec_result_t result;
    if (detexec_replay(ctx, trace, &result) != 0) {
        fprintf(stderr, "Replay failed\n");
        return 1;
    }
    
    printf("Replay completed successfully\n");
    printf("Output hash matches: %s\n", 
           result.output_verified ? "yes" : "no");
    
    detexec_free_trace(trace);
    detexec_free(ctx);
    return 0;
}

Python API

from deterministic_executor import DetExec, DetExecConfig

# Configure deterministic execution
config = DetExecConfig(
    deterministic_time=True,
    deterministic_entropy=True,
    record_execution=True,
    output_path='execution.trace'
)

# Execute deterministically
executor = DetExec(config)
result = executor.exec(['/usr/bin/myapp', '--option'])

print(f"Exit code: {result.exit_code}")
print(f"Trace hash: {result.trace_hash}")

# Later: replay execution
trace = DetExec.load_trace('execution.trace')
replay_result = executor.replay(trace)

assert replay_result.output_verified

API Reference

Context Management

detexec_new()

Create a new deterministic execution context.

detexec_free(ctx)

Free a context and release resources.

detexec_set_config(ctx, config)

Configure deterministic execution parameters.

Execution

detexec_exec(ctx, path, argv, result)

Execute a program deterministically.

detexec_exec_with_env(ctx, path, argv, envp, result)

Execute with custom environment.

detexec_spawn(ctx, path, argv, pid_out)

Spawn a deterministic process.

Recording

detexec_start_recording(ctx, output_path)

Start recording execution trace.

detexec_stop_recording(ctx)

Stop recording and finalize trace.

detexec_get_trace_stats(ctx, stats)

Get statistics about recorded trace.

Replay

detexec_load_trace(path)

Load a trace file.

detexec_replay(ctx, trace, result)

Replay a recorded execution.

detexec_replay_partial(ctx, trace, until_event, result)

Replay up to a specific event.

Verification

detexec_verify_trace(trace)

Verify cryptographic integrity of trace.

detexec_compute_trace_hash(trace, hash_out)

Compute hash of execution trace.

detexec_sign_trace(trace, private_key)

Sign trace with private key.

detexec_verify_signature(trace, public_key)

Verify trace signature.

Time Control

detexec_set_virtual_time(ctx, time)

Set the virtual time for execution.

detexec_set_time_scale(ctx, scale)

Set time scaling factor (1.0 = normal).

Entropy Control

detexec_set_seed(ctx, seed)

Set deterministic random seed.

detexec_set_entropy_source(ctx, callback)

Set custom entropy source.

Configuration Options

Basic Configuration

typedef struct {
    bool deterministic_time;        /* Virtualize time */
    bool deterministic_entropy;     /* Control randomness */
    bool deterministic_signals;     /* Deterministic signal delivery */
    bool deterministic_threads;     /* Deterministic thread scheduling */
    bool record_execution;          /* Record trace */
    const char *output_path;        /* Trace output file */
    uint64_t virtual_time_start;    /* Starting virtual time */
    uint64_t random_seed;           /* Random seed */
} detexec_config_t;

Advanced Configuration

typedef struct {
    bool record_syscalls;           /* Record all syscalls */
    bool record_io;                 /* Record I/O operations */
    bool record_network;            /* Record network traffic */
    bool record_filesystem;         /* Snapshot filesystem state */
    bool cryptographic_verification;/* Enable crypto verification */
    const char *hash_algorithm;     /* Hash algorithm (SHA256, etc.) */
    bool enable_compression;        /* Compress trace files */
    size_t max_trace_size;          /* Maximum trace size */
} detexec_advanced_config_t;

Usage Examples

Reproducible Build

#include <deterministic-executor/detexec.h>

int reproducible_build(const char *source_dir, const char *output_dir) {
    detexec_context_t *ctx = detexec_new();
    
    detexec_config_t config = {
        .deterministic_time = true,
        .deterministic_entropy = true,
        .virtual_time_start = 0,  // Unix epoch
        .random_seed = 42,
        .record_execution = true,
        .output_path = "build.trace"
    };
    
    detexec_set_config(ctx, &config);
    
    // Execute build command
    const char *argv[] = {
        "make",
        "-C", source_dir,
        "OUTPUT=" output_dir,
        NULL
    };
    
    detexec_result_t result;
    int ret = detexec_exec(ctx, "/usr/bin/make", argv, &result);
    
    if (ret == 0) {
        printf("Build completed deterministically\n");
        printf("Build hash: %s\n", result.trace_hash);
    }
    
    detexec_free(ctx);
    return ret;
}

Forensic Analysis

#include <deterministic-executor/detexec.h>

void analyze_incident(const char *trace_path) {
    detexec_trace_t *trace = detexec_load_trace(trace_path);
    
    // Verify trace hasn't been tampered with
    if (!detexec_verify_trace(trace)) {
        fprintf(stderr, "Trace integrity check failed!\n");
        return;
    }
    
    // Extract syscall sequence
    detexec_event_t *events;
    size_t count;
    detexec_get_events(trace, &events, &count);
    
    printf("Analyzing %zu events\n", count);
    
    for (size_t i = 0; i < count; i++) {
        if (events[i].type == DETEXEC_EVENT_SYSCALL) {
            printf("Syscall: %s at time %lu\n",
                   events[i].syscall.name,
                   events[i].timestamp);
        }
    }
    
    detexec_free_trace(trace);
}

Deterministic Testing

#include <deterministic-executor/detexec.h>

bool test_race_condition() {
    detexec_context_t *ctx = detexec_new();
    
    detexec_config_t config = {
        .deterministic_threads = true,
        .deterministic_signals = true,
        .random_seed = 12345
    };
    
    detexec_set_config(ctx, &config);
    
    // Run test with deterministic scheduling
    const char *argv[] = {"./race_test", NULL};
    detexec_result_t result;
    
    detexec_exec(ctx, "./race_test", argv, &result);
    
    // The same race condition will happen every time
    bool test_passed = (result.exit_code == 0);
    
    detexec_free(ctx);
    return test_passed;
}

Integration Examples

With process-sandbox

#include <process-sandbox/sandbox.h>
#include <deterministic-executor/detexec.h>

// Combine sandboxing with deterministic execution
sandbox_config_t sandbox = sandbox_config_new();
sandbox_config_set_namespaces(&sandbox, SANDBOX_NS_ALL);

detexec_context_t *detexec = detexec_new();
detexec_config_t config = {
    .deterministic_time = true,
    .deterministic_entropy = true,
    .record_execution = true
};
detexec_set_config(detexec, &config);

// Execute in sandbox with determinism
sandbox_config_set_detexec(&sandbox, detexec);
sandbox_exec(&sandbox, "/usr/bin/untrusted", argv, NULL);

Cryptographic Attestation

#include <deterministic-executor/detexec.h>

void create_execution_attestation(const char *trace_path) {
    detexec_trace_t *trace = detexec_load_trace(trace_path);
    
    // Compute merkle tree of execution
    detexec_merkle_tree_t *tree = detexec_build_merkle_tree(trace);
    
    // Get root hash (attestation)
    uint8_t root_hash[32];
    detexec_merkle_root(tree, root_hash);
    
    printf("Execution attestation: ");
    for (int i = 0; i < 32; i++) {
        printf("%02x", root_hash[i]);
    }
    printf("\n");
    
    // Sign attestation
    detexec_sign_trace(trace, "private_key.pem");
    detexec_save_trace(trace, "signed_trace.trace");
    
    detexec_free_merkle_tree(tree);
    detexec_free_trace(trace);
}

Trace Format

Execution traces are stored in an efficient binary format:

Trace File Format:
┌──────────────────────┐
│ Header               │
│  - Magic bytes       │
│  - Version           │
│  - Config            │
│  - Start timestamp   │
│  - Metadata          │
├──────────────────────┤
│ Event Stream         │
│  - Event 1           │
│  - Event 2           │
│  - ...               │
│  - Event N           │
├──────────────────────┤
│ Cryptographic Data   │
│  - Hash chain        │
│  - Merkle tree       │
│  - Signature         │
└──────────────────────┘

Building

Requirements

• Linux kernel 4.0+
• libssl-dev (for cryptography)
• libz-dev (for compression)
• GCC 9+ or Clang 10+

Build Commands

# Build library
make

# Build with debug symbols
make DEBUG=1

# Run tests
make test

# Install
sudo make install

Performance

• Recording overhead: 5-15% execution time
• Replay speed: 1.5-3x faster than original execution
• Trace size: ~1-10 MB per minute of execution (compressed)
• Verification time: <100ms for typical traces

Sources of Non-Determinism

The executor controls:

1. Time: gettimeofday(), clock_gettime(), etc.
2. Randomness: /dev/random, /dev/urandom, getrandom()
3. Thread Scheduling: Deterministic thread interleaving
4. Signal Delivery: Deterministic signal timing
5. Memory Addresses: ASLR disabled/virtualized
6. PIDs/TIDs: Virtualized process/thread IDs
7. File System: Snapshots and timestamps
8. Network: Order of packet delivery

Troubleshooting

Non-deterministic results

Check for uncontrolled sources:

detexec-analyze --check-determinism execution.trace

Trace verification fails

Verify trace wasn't modified:

detexec-verify execution.trace

Large trace files

Enable compression:

config.enable_compression = true;

Security Considerations

1. Trace Integrity: Always verify trace signatures
2. Private Keys: Protect signing keys
3. Sensitive Data: Traces may contain sensitive information
4. Replay Safety: Replay in isolated environments
5. Time Rollback: Virtual time can be in the past

Contributing

See CONTRIBUTING.md

License

MIT License - See LICENSE

References

• Deterministic Process Groups in TreadMarks
• rr: Record and Replay
• Determinator: OS for deterministic execution
• Time Travel Debugging

Standalone Installation

git submodule add https://github.com/navinBRuas/_SecureExecutionEnvironment.git vendor/secure-execution

Use vendor/secure-execution/deterministic-executor for local builds and integration.

Usage

Follow the C or Python examples above and module headers for full API details.

Configuration

Configure determinism, tracing, and verification via detexec_config_t and advanced config structs.

Version

Current version: 0.1.0 (see VERSION.md).

Changelog

See CHANGELOG.md for release history.