generate_bin_search_bpf.py

#! /usr/bin/env python3

"""
Generates a binary search BPF seccomp program for a blacklist of system call
numbers specified as space-separated integers in stdin.

Example:

$ echo 1 3 6 8 13 | ./generate_bin_search_bpf.py
ld [0]
jeq #6, bad
jgt #6, check8
jeq #1, bad
jeq #3, bad
ret #0x7fff0000
check8:
jeq #8, bad
jeq #13, bad
ret #0x7fff0000
bad: ret #0
"""

def intro(X, J):
        s = ""
        s += "jeq #%d, bad\n" % X
        s += "jgt #%d, check%d\n" % (X, J)
        return s

def linear(L):
        s = ""
        for X in L:
                s += "jeq #%d, bad\n" % X
        s += "ret #0x7fff0000\n"
        return s

def jump_label(X):
        return "check%d:\n" % X

def program(L):
        N = len(L)
        if N <= 2:
                return linear(L)

        M = N // 2
        return intro(L[M], L[M+1]) + program(L[:M]) + jump_label(L[M+1]) + program(L[M+1:])

L = sorted(list(map(int, input().split())))
print ("ld [0]\n" + program(L) + "bad: ret #0")