GreyCTF 2023 Finals: StackVM

Table of Contents

This is the author’s writeup for the challenges StackVM in the misc category.

This describes the intended solution when I made the challenge.

Challenge Description #

Here is my StackVM. Can you implement Fibonacci in it?

You will get a flag when you complete all 35 test cases.

Score Board prizes will be added at the end of the round 1st: 300 pts 2nd: 200 pts 3rd: 100 pts

Bonus points: +50 points if you beat the NUS Greyhats Score (Credits to Ariana)

Junhua

A file was provided with the StackVM implementation

My Notes #

This was meant to be a challenge for those who manage to full solve the CTF and want to find something else to do.
The mechanism to submit for any team was intended.
I was actually looking to see if anyone would try to bump up the score of NUS Greyhats to prevent others from getting the bonus points.
This challenge came about when we were thinking of ways to make the challenges harder for the teams that were doing well.

Notes to future self when setting up this challenge. #

Have multiple milestones when setting up the challenge.
Have different categories for participants to submit their solutions for different code.

Fun Fact: We wanted to make a transpiler challenge and have another VM architecture for Day 2 but thought that it was too toxic for the participants who did not do the challenge in day 1.

The challenge #

Looking at the distributed vm, we can see that the vm is a stack based vm with the following instructions.

NAND - ~(a & b)
JNE - Jump to target if top of stack is not 0
JE - Jump to target if top of stack is 0
SWAP - Swap the top of stack with the value at the index
DUP - Duplicate the top of stack
SHIFT - Shift the top of stack left by the value below it
PUSH - Push a value onto the stack
POP - Pop a value from the stack

Constraints #

There is a limit to the maximum number of line executions as 150000 for each execution.
There is also a code limit of 1000 lines of code. Any more will result in an auto wrong answer
After the execution of the code, the answer to fibonacci should be placed at the top of the Stack.

Challenges #

The assembly instructions do not contain any arithmetic instructions. Any operators will have to be implemented using the NAND instruction.
The fibonacci calculation has many different implementations and we will have to find the one which takes the least number of instructions.
The VM is implemented in python, there are some python perks that applies to this VM

Tricks that can be used #

Calling the Swap instructions with a negative index (-1) allows the item to be placed to the bottom.
NAND in the VM does the NAND for all the bits in the number at once.
A trivial way to solve some test cases can be just 1 instruction DUP which will just duplicate the top of stack.

Intended solution #

Work the way up from Primitives and get the solution

One possible solution is shown below.

For those who are interested in solving this problem, I have created an instance of the challenge here.

Useful Links #

Distributed Code #

from typing import List

class StackVM(object):
    def __init__(self: 'StackVM') -> None:
        self.stack = []
        self.pc = 0  # Program counter
        self.line_execution = 0  # Length of execution
        self.max_execution = 150000  # Max length of execution

    def _push(self, value: int) -> None:
        self.stack.append(value)

    def _pop(self) -> None:
        if self.stack:
            return self.stack.pop()
        else:
            raise IndexError("Stack is empty")

    def _nand(self) -> None:
        if len(self.stack) >= 2:
            a = self._pop()
            b = self._pop()
            result = ~(a & b)
            self._push(result)
        else:
            raise IndexError("Insufficient operands on the stack")

    def _jne(self, target) -> None:
        if self._pop() != 0:
            self.pc = target

    def _je(self, target) -> None:
        if self._pop() == 0:
            self.pc = target

    def _swap(self, to, fro) -> None:
        if len(self.stack) >= 2:
            tmp = self.stack[-1-fro]
            self.stack[-1-fro] = self.stack[-1-to]
            self.stack[-1-to] = tmp
        else:
            raise IndexError("Insufficient operands on the stack")

    def _dup(self) -> None:
        if self.stack:
            self._push(self.stack[-1])
        else:
            raise IndexError("Stack is empty")

    def _shift(self) -> None:
        if len(self.stack) >= 2:
            a = self._pop()
            b = self._pop()
            result = (b << a)
            self._push(result)
        else:
            raise IndexError("Insufficient operands on the stack")

    def _execute(self, bytecode: List[str]) -> None:
        while self.pc < len(bytecode):
            instruction = bytecode[self.pc]

            if self.line_execution > self.max_execution:
                raise Exception("Max execution length reached")

            self.pc += 1
            self.line_execution += 1

            if instruction == "NAND":
                self._nand()
            elif instruction.startswith("JNE"):
                target = int(instruction[3:])
                self._jne(target)
            elif instruction.startswith("JE"):
                target = int(instruction[2:])
                self._je(target)
            elif instruction.startswith("SWAP "):
                _, arg1, arg2 = instruction.split(" ")
                self._swap(int(arg1), int(arg2))
            elif instruction == "DUP":
                self._dup()
            elif instruction == "SHIFT":
                self._shift()
            elif instruction.startswith("PUSH"):
                value = int(instruction[4:])
                self._push(value)
            elif instruction == "POP":
                self._pop()
            else:
                raise ValueError("Invalid instruction: " + instruction)

    def _reset(self) -> None:
        self.line_execution = 0
        self.pc = 0
        self.stack = []

    @staticmethod
    def compile(program: str) -> List[str]:
        """Compile this program into bytecode"""
        return list(
            filter(
                lambda x: len(x) > 0,
                map(
                    lambda x: x.strip().upper(),
                    program.split("\n")
                )
            )
        )

    def run(self: 'StackVM', bytecode: List[str], args: List[int]) -> int:
        """Returns final answer on stack and number of instructions in code"""
        # Code cannot be too long (Prevent hard coding)
        if len(bytecode) > 1000:
            return -1

        self._reset()
        for i in args:
            self.stack.append(i)
        try:
            self._execute(bytecode)
        except:
            pass
        return self.stack[-1] if len(self.stack) > 0 else -1

One possible solution #

PUSH 1
PUSH 0
SWAP 0 -1
DUP
JE 56
SWAP 0 -1
DUP
DUP
SWAP 0 3
DUP
SWAP 1 2
NAND
DUP
DUP
SWAP 0 4
NAND
SWAP 0 2
NAND
NAND
SWAP 0 1
DUP
NAND
PUSH 1
SHIFT
SWAP 0 1
DUP
SWAP 0 2
DUP
JNE 9
POP
POP
SWAP 0 -1
PUSH 1
DUP
SWAP 0 2
DUP
SWAP 1 2
NAND
DUP
SWAP 0 2
NAND
SWAP 0 2
NAND
DUP
DUP
NAND
SWAP 0 2
NAND
SWAP 0 1
PUSH 1
SHIFT
DUP
JNE 33
POP
PUSH 0
JE 3
POP
POP