A look into the “calcql” challenge from SekaiCTF 2024
TL;DR:
The challenge goal is to provide CodeQL script finds specific function that returns 42 and would be run over some auto-generated random python code.
The solution should be CodeQL that statically analyze auto-generated random python code and evaluate only the function that returns 42
Our Solution combines several CodeQL analyzing techniques like: Using Call objects, doing recursive static analysis and more .
Let’s dive in
In SekaiCTF 2024, there was a medium-level miscellaneous challenge focused on CodeQL, that had 32 solutions initially. The challenge description was “Use CodeQL to find the function that returns 42.” Behind the scenes, there’s a program that generates a python script which defines many functions. The first functions are defined so their return value is some simple integer addition expression. As more functions were defined, their return value remains an additional expression though some of the added values are the previously defined functions. This eventually results in big, coupled script with many functions that return seemingly random numbers.
We need to send some CodeQL query to a server that will run it and check whether the query returns the name of the 42-function. If our query outputs the correct function name, we succeed and get the flag. Each try a new random “addition script” is generated and our only access to it is with our CodeQL query. Another small point is that our CodeQL needs to work correctly for two random scripts probably to mitigate from accidental correct solutions.
What do we need to do?
So obviously we need to write a CodeQL script that will output the name of a function that returns 42. However, we came to this challenge without prior experience with CodeQL, all we knew is that it’s a query language that’s meant to find patterns within codebases. First, we jumped to find basic examples of CodeQL to get an idea of what should be our approach. Seeing some basic examples like finding “Authorization” decorators on function/classes we started to get the hang of CodeQL. We noted the general structure of CodeQL with its from-where-select clauses that are meant to work like a select query in SQL. It works like this:
- First, ‘from’ is used to specify the “language object” you want to use like ‘Function’, and you give a name to the instance you will be working with like ‘f’. You can have multiple such instances too.
- Then we can use ‘where’ to filter between the instances like checking the function name to start with entry: “f.getName().prefix(5) = “entry”. Notice this doesn’t use the usual ‘==’ as there are no assignment operators in the language, but it works using associations, we will see more later.
- Then ‘select’ is used to select the specific info we want to output like:
“select f, f.getName()”
Here is the result of such a query:
Then CodeQL aims to allow you to make such queries with more complicated logic to find the specific patterns you are looking for: if it is making sure you have added an authentication check everywhere you need, trying to spot where some bug could have occurred by querying the specific structures, etc.
Understanding the challenge
Here we came to the main obstacle, it seemed that CodeQL is generally intended to find patterns within code by using the Abstract Syntax Tree of a language. This is a problem as getting return values of functions is something that CodeQL is not meant to do. It only analyses the code statically. Then how do we still extend those examples to our situation? The answer lies in the fact that the generated code is entirely static. That is, all the outputs are not dependent on user input. We could make a CodeQL query that works as an evaluator. It will traverse through every function and recursively calculate it somehow and eventually get its numerical return value. After we have all the return values, we can easily filter out the function that will output 42.
Building the solution
All that being said, at that point, we still didn’t fully know how to use this language, and many times we couldn’t find exactly what we wanted to do in the documentation. Because of that we mainly were looking at random components of the language. We learned the language gradually until we could write our final CodeQL script.
The first object that caught our eyes was the ‘BinaryExpr’ object, As the name suggests it holds two expressions and the operator that acts on them. We couldn’t just simply find the one with the value 42 as again CodeQL only analyzes the syntax tree and won’t evaluate anything itself. Even if we could do so, using ‘BinaryExpr’ alone we won’t be able to easily tell that it’s the outermost BinaryExpr.
For now, we had to find a way to associate the ‘BinaryExpr’ to a function’s return expression. After some more digging, we found an object called ‘Return’, this object held the expression that the function returns. In our case the ‘Return’ objects almost always held a ‘BinaryExpr’ that represented the addition of the different terms. Now we needed to associate the ‘Return’ to the function’s name. Using the IntelliSense we quickly wrote a simple script that does exactly that and it worked:
Amazing! So now we need to find a way to calculate the ‘BinaryExpr’ with CodeQL. The idea was quite simple: build a function that recursively checks if the left side of the ‘BinaryExpr’ is also a ‘BinaryExpr’. If it’s not, we reached the end and we can just return the value; But if it is, we call the function recursively on the next ‘BinaryExpr’. After some research we successfully wrote a script that uses predicates which are CodeQL’s version of functions. In our case we have a predicate that takes a BinaryExpr and checks the left side as we explained and calls itself accordingly and adds the right side to it until the left side is and integer and it will stop the recursion. Here is the part that finishes the recursion for example:
But there was still one thing we had to solve. Currently, the script would work well for functions that are only adding integers. Though, sometimes we need to add the result of other functions in the expression. In those cases, we need to calculate their value too. When a function appears in the BinaryExpr it appears as a ‘Call’ object which hold function calls, if we could associate it to its ‘Return’ object we could recursively call the evaluating predicate on it. Eventually we just found a way to gain the ‘Return’ object of the function using a nice concept in CodeQL:
In CodeQL the return value of a predicate is called “result” and instead of having to define it like a variable, we can associate it to other objects. Here the code basically says: “result is a ‘Return’ object whose function name needs to match ‘Call’s function name”. Again, we notice how the ‘=’ sign is used like a condition, and it is – it notes to the language that out of all the ‘Return’ object we want the one that satisfies this condition. Here is the part that handles the left side being integer and the right side being a function call:
Finalizing the solution
Now we had all the components to write the final script. The final script itself does what we described earlier in the following way: we separated to cases all the types that the left and right side of the ‘BinaryExpr’ can be(‘Call’, ‘IntegerLiteral’, ‘BinaryExpr’), then extract the value according to the required method and just add the value.
The final query
