This is a writeup for the “calcql” challenge I authored for SekaiCTF 2024.

Setup

Provided was a server that generates two randomized Python files and builds a CodeQL database from each. The python files define a set of functions, one of which returns the value 42. The function names and bodies are randomized. Players could then POST their solver as a .ql file to /submit, which the server would then run against both databases. The flag is returned if the output matches the stored “42” function name for both.

app.py:

@app.route("/submit", methods=["POST"])
def submit():
    query = request.json.get("query")

    for i in range(0, 2):
        basedir = f"/opt/db/{i}"
        expected = open(f"{basedir}/hash").read()
        open(f"{basedir}/query.ql", "w").write(query)
        ch = Popen(
            ["codeql", "query", "run", "-q", "-d", f"{basedir}/db", f"{basedir}/query.ql"],
            stdout=-1, cwd=basedir,
        )
        streamdata = ch.communicate()[0]
        rc = ch.returncode
        if rc:
            return jsonify({"error": streamdata.decode()})

        lline = streamdata.decode().splitlines()[-1]
        match = re.search(r"entry_[0-9a-f]{20}", lline)
        if not (match and expected == match.group(0)):
            return "fail"

    return FLAG

The generated program

shuffler.py builds the database at server startup. It first generates a set of helper fn_ functions returning small constants (1, 2, 5) and combinations:

for n in [1, 2, 5]:
    (_, f) = self.gen_func(n, "fn")
    self.gen[n] = n

for _ in range(0x100):
    sum = random.randint(10, 0x100)
    body = " + ".join(map(str, self.generate_sum(sum)))
    (fname, f) = self.gen_func(body, "fn")
    if sum not in self.gen:
        self.gen[sum] = fname + "()"
        self.src.append(f)

Then it generates one entry_ function for every integer from 1 to 1023:

for sum in range(1, 0x400):
    body = " + ".join(map(str, self.generate_sum(sum)))
    (fname, f) = self.gen_func(body, "entry")
    if sum == 42:
        self.hash = fname
    self.src.append(f)

generate_sum decomposes a target into a sum of previously registered values, mixing integer literals and calls to fn_ functions. The result looks like:

def entry_3f8a1c...:
    return fn_a1b2c3...() + 5 + fn_d4e5f6...() + 2

All functions are shuffled before writing to main.py, so the name is the only thing that identifies which function returns 42.

Why a naive query doesn’t work

The return value is never a literal 42, it’s always a mix of integer literals and calls to other functions. A query that just looks for return 42 or checks IntegerLiteral directly won’t find it.

You need to recursively evaluate each function’s return value by summing all integer literals it contains and adding the evaluated return values of all called functions.

Solve

The key is using a recursive CodeQL predicate with language[monotonicAggregates].

Standard CodeQL rejects recursive aggregates (like sum) because they can be non-terminating in the general case. The monotonicAggregates annotation opts in to a mode where CodeQL allows recursion inside aggregates, requiring that the aggregate is monotonically non-decreasing across iterations, which holds here since all values are positive integers.

solve.ql:

import python

language[monotonicAggregates]
int dcount(Function f) {
  result =
    sum(IntegerLiteral i | f.contains(i) | i.getValue()) +
      sum(Call c, Function fn |
        c.getFunc().(Name).toString() = fn.getName() and f.contains(c)
      |
        dcount(fn)
      )
}

from Function f
where
  f.getName().prefix(6) = "entry_" and
  dcount(f) = 42
select f.getName(), dcount(f)

dcount(f) recursively computes the total return value of f by:

  1. Summing all IntegerLiteral values directly inside f
  2. For each Call inside f resolving to another Function fn, adding dcount(fn)

The where clause then filters to entry_ functions where that sum equals 42.