Devlog #3 | I have grown taller from walking with the trees 🌳

β€œToday I have grown taller from walking with the trees.”

― Karle Wilson Baker

tree

Welcome back to my devlog series, where I discuss the development of make-git-better version 2 - a git CTF challenge. Last time we finished developing a script that automated generating the main git server hook for the CTF.

Today we’re automating another big part of the challenge: creating the level browser.

Why do we need a level browser?

When solving a CTF, I want to make sure I keep the fun/frustration factors pretty balanced. To that end, I want to communicate some things to the player, such as:

  1. If you’re stuck on a level, here are some hints.
  2. The storyline/theme/flavour/jokes/memes are there if you want them; out of the way if you don’t.
  3. You’ve made X progress and you are Y level away from finished the challenge.

I feel like knowing all this really lowers the risk of the player getting frustrated while playing the CTF, so we can avoid unpleasentenss

Computer rage

Also, potentially, it would be cool to have a place to put your flags and get the next level/a code to the “final” level.

So I need a place to put auxiliary content for each level. The options were either in the level itself as text files that are a part of the game repository or as a separate webpage. I decided to go with a webpage since combining the two seemed to not really work in the last version of this challenge and webpages allow for more content types to be easily embedded. A good example of a CTF doing this is OverTheWire.

OverTheWire Level Browser

OverTheWire Level Browser

However, unlike OverTheWire, the level structure in this CTF is not linear, so the level browser can’t just be a list. Logically, it’s an Arborescence: a directed, acyclic, rooted tree 🌳 graph where the Nodes are levels and the Edges are flags. I drew some inspiration from Google’s beginner CTF page:

Google CTF Level Browser

Google CTF Level Browser

And set out to implement it myself.

High-level design: level browser generator

TL;DR

Shove the game config (TOML file with a list of levels) into a visual interactive web graph file, and embed that file in the CTF site.

More details

Input: The game’s configuration, which looks like this:

[[levels]]
  title = "clone"
  branch = "master"
  solution_checker = "echo No pushing to master. Read the README file; exit 1"
  flags = ["start-here"]

[[levels]]
  title = "start-here"
  branch = "start-here"
  solution_checker = "hooks/checkers/start-here.sh"
  flags = ["merge-1"]

[[levels]]
  title = "merge-1"
  branch = "REDACTED"
  solution_checker = "hooks/checkers/merge-1.sh"
  flags = ["merge-2", "log-1"]
...

Will be fed into a script that parses it into a graph. The script will then render the graph to the…

Output: an interactive level browser that looks like a graph.

How will the script work

There are two heavy lifting jobs in this script and a lot of boilerplate that surrounds them. The first job is taking the config and parsing it into a graph. The second job is displaying the logical graph in a web context.

To solve the first job, we’ll write a recursive algorithm in Rust and parse the config Level by Level. To solve the second job, we’ll use some nifty JS libraries and standard languages to “shove” the graph into a web page.

Implementation

Refactoring the project structure

Professor rework dropped in for a visit…

Last time we created some data structures that represent a single Level and the Game Config, but it was all in a single file. Now that we’re planning to write another script, it’ time to move stuff out of single files into a common library under /lib and separate different scripts into different files under a /bin. This resulted in the following directory structure:

# This is executable scripts
/scripts/src/bin
/scripts/src/bin/generate-levels-graph.rs
/scripts/src/bin/generate-pre-receive-hook.rs

# This is common code
/scripts/src/lib
/scripts/src/lib/lib.rs

Parsing the configuration into a graph

Who would have believed that I would actually need to write a recursive algorithm that deals with Graphs outside of university?

Happy student

The core algorithm of the script is add_level_nodes_to_graph, which is a recursive function that gets the current level and adds the next levels from it (i.e. the current level’s flags, if those point to other levels) to the graph - and calls itself again for each of those levels. The graph is initialized with the root.

While developing this part, I really struggled with the concept of ownership and lifetimes in Rust. However, after a few hours of frustrating debugging, the Rust community really helped me figure those issues out (which is why you see a lot of .clone()s dotted around the code).

Here’s the code:

fn create_graph_from_game_config(game_config: &GameConfig) -> LevelsGraph {
    let mut levels_graph = LevelsGraph::new();

    let first_level = game_config.levels[0].clone();
    let tree_root = levels_graph.add_node(first_level.clone());
    add_level_nodes_to_graph(first_level, &tree_root, &mut levels_graph, &game_config);

    levels_graph
}

/// Recursive function that populates the game graph
///
/// If receives a graph initialized with the first level as a root node.
fn add_level_nodes_to_graph<'a>(
    current_level: Level,
    current_node: &'a NodeIndex,
    levels_graph: &'a mut LevelsGraph,
    game_config: &'a GameConfig,
) {
    if current_level.flags.len() == 0 {
        return;
    };

    for flag in current_level.flags {
        debug!("level {} flag {}", current_level.title, flag);
        let mut levels_iterator = game_config.levels.iter();
        let found = levels_iterator.find(|x| x.title == flag);
        match found {
            Some(x) => {
                debug!(
                    "The flag does point to another level, {}. Adding level as node to graph",
                    x.title
                );
                let new_node = levels_graph.add_node(x.clone());
                debug!("Adding edge from {} to {}", current_level.title, x.title);
                levels_graph.add_edge(*current_node, new_node, 0);
                debug!("Recursive calling add nodes on {}", x.title);
                add_level_nodes_to_graph(x.clone(), &new_node, levels_graph, &game_config);
            }
            None => {
                debug!("The flag doesn't point to another level - no need to recurse");
            }
        }
    }
}

Example

Let’s run through an example (this example is the unit test, as well). Let’s say this is our game config:

let first_level = Level {
    title: String::from("first"),
    branch: String::from("first"),
    solution_checker: String::from("first"),
    flags: vec!["second".to_string()],
};
let second_level = Level {
    title: String::from("second"),
    branch: String::from("sec"),
    solution_checker: String::from("sec"),
    flags: vec!["another".to_string(), "asdf".to_string()],
};

let game_conf = GameConfig {
    levels: vec![first_level, second_level],
};

Now, when we call let graph = create_graph_from_game_config(&game_conf);, the graph is initialized with the first level as its root. This is how the graph looks like at this state:

graph 1

After initializing we call add_level_nodes_to_graph with the first node as a parameter. add_level_nodes_to_graph iterates on all of the first level’s flags. Since second is the title of another level, it is added to the graph and an edge is drawn between first and second. This is how the graph looks like at this state:

graph 2

The second level has 2 flags, but these flags don’t actually “point” to other levels that exist in the configuration - so add_level_nodes_to_graph discards them as flags that don’t shouldn’t be nodes in the final graph. We’re done with that call, the stack unwinds, and we wind up with a simple Tree graph.

Rendering the graph as an interactive web UI element

To do this, I had to first take into consideration the fact that all of the game’s web content will be part of my blog and therefore it should work neatly in Hugo. I decided that the level browser will be a custom Hugo shortcode and to use the vis.js JS library to display the graph itself. The interface between the logical graph in the script and the actual resulting HTML file had two parts - TinyTemplate for the actual string replacement, and DOT as the common language.

Outputting the graph to DOT

The petgraph crate has built-in support for DOT, so outputting the graph to DOT format was very easy:

let levels_graph_as_dot = Dot::with_config(&levels_graph, &[Config::EdgeNoLabel]);

The resulting DOT string is very readable:

digraph {
    0 [label="clone"]
    1 [label="start-here"]
    2 [label="merge-1"]
    3 [label="merge-2"]
    4 [label="log-1"]
    5 [label="log-2"]
    0 -> 1
    1 -> 2
    2 -> 3
    2 -> 4
    4 -> 5
}

Using the DOT string to render a visual, interactive graph

The graph template file (which becomes a shortcode) has a few interesting parts. First, it has an empty div with the “mynetwork” id:

<div id="mynetwork"></div>

Then the script starts doing the heavy lifting. First we define the DOTstring using TinyTemplates built-in unescaped formatter and parse the data using vis:

    var DOTstring = `
{levels_graph_as_dot | unescaped}
`;
    var parsedData = vis.parseDOTNetwork(DOTstring);

    var data = \{
      nodes: parsedData.nodes,
      edges: parsedData.edges
    }

After we have the data, we can create the graph itself. There are a lot of styling options here to make the graph itself look nice:

    // create a network
    var container = document.getElementById('mynetwork');

    var options = \{
      autoResize: true,
      nodes: \{
        shape: "box",
        shadow: true,
        color: "#e8eef2",
        font: "20px arial black"
      },
      edges: \{
        color: "#e8eef2",
      },
      physics: \{
        enabled: true,
        solver: "hierarchicalRepulsion",
      },
      layout: \{
          hierarchical: \{
            direction: "LR",
            levelSeparation: 100,
            nodeSpacing: 33,
        }
      }
    };

    // initialize your network!
    var network = new vis.Network(container, data, options);

Finally, we need to add interactivity to the graph - otherwise, it’s not a level browser! Luckily, it was rather simple to use vis.js’s detailed code examples to build this:

    network.on("click", function(params) \{
        if (1 == params.nodes.length) \{
            levelName = data.nodes[params.nodes[0]].label;
            resulting_url = document.location.origin + "/levels/" + levelName;
            document.location.href = resulting_url;
        }
    });

And the final result looked pretty cool :)

level browser demo

Unit testing

I also covered the non-boilerplate parts of the code with unit tests. Since rust has it baked-in to the language and tooling, this is very easy and immediately satisfying.

"Test Explorer"

The unit test for this script was the example we saw eariler:

#[cfg(test)]
mod tests {
    use super::*;
    use petgraph::algo::is_cyclic_directed;

    #[test]
    fn test_create_graph_from_game_config() {
        let first_level = Level {
            title: String::from("first"),
            branch: String::from("first"),
            solution_checker: String::from("first"),
            flags: vec!["second".to_string()],
        };
        let second_level = Level {
            title: String::from("second"),
            branch: String::from("sec"),
            solution_checker: String::from("sec"),
            flags: vec!["another".to_string(), "asdf".to_string()],
        };

        let game_conf = GameConfig {
            levels: vec![first_level, second_level],
        };
        let graph = create_graph_from_game_config(&game_conf);

        assert_eq!(graph.node_count(), 2);
        assert_eq!(graph.edge_count(), 1);
        assert!(graph.is_directed());
        assert!(!is_cyclic_directed(&graph));
    }
}

What’s next

Now that a lot of the infrastructure is in place, it’s time to plan out, develop, test, deploy, test again, and write content for all of the levels. The previous version of the challenge had about 11 levels all in all. I hope to get to at LEAST 15 in the first iteration - hopefully, 20.

But that’s for tomorrow, and tomorrow is another day…

Weekend