Leveraging Python's parser to safely evaluate user-submitted formulas

Let's say you're working on an application that calculates a specific parameter on a regular basis and this parameter defines its work. It can be the player score used to rate players on a leaderboard, or it can be a filtering condition for the products to be featured on the home page. This value is calculated with a formula, and you want your users to be able to customize the formula and tweak the application's behavior.

If you absolutely trust your users to be non-malicious and competent (for example, if they are hired to maintain the site, or if it's your personal project and you're the only user), and you're up for a quick solution, you can get away with treating formulas like Python code and running them with eval.

Of source, in most cases users are not that trustworthy, so you might be planning to use a third-party formula parser or roll out your own. But you don't have to! If you're okay with your formula language being a subset of Python, you can take a shortcut and use Python's parser to convert formulas into Abstract Syntax Trees (AST). Then you can feed the AST into your own small interpreter that has a whitelist of Python features that you're willing to support, – effectively, a "safe eval".

In this post, I'll demonstrate an example implementation of a small formula engine built on top of the ast package that comes with Python's standard library and provides access to Python's parser.

Parsing

To parse a formula with the ast package, call ast.parse:

import ast

formula = "(a + b) * 2"
node = ast.parse(formula, "<string>", mode="eval")

It accepts the source code as the first and the only required argument.

The second argument is the name of the file that you're parsing. This name will be displayed in the stack trace of syntax errors. In our case, it's not important, but it's common to use <string> when the source is not coming from a file.

The mode parameter restricts the content of the source. "eval" mode requires that the source contains a single expression (that is, a piece of code that produces a value, in opposition to "statement" which is a piece of code that performs some sort of operation but doesn't have to evaluate to a value). If the source is not an expression, parse will raise SyntaxError. This is perfectly fit for formula parsing.

Other modes include "exec" – expecting the string to contain multiple statements as in a normal Python script, and "single" – expecting a single "interactive" statement. More on this in the docs.

The parse function returns an AST node – an object representing a section of the code. In "eval" mode, the returned node will be an ast.Expression object. We'll look into its inner structure shortly.

Let's say we want to support number literals (3.14) and variables (pi), plus addition, subtraction, negation, multiplication, and division for operations. We can use the ast.dump function to print the whole syntax tree to see what this syntax looks like in AST form. Let's make a test formula containing every feature we want and parse it:

>>> node = ast.parse("(a + 1) - (2 * 3 / -4)", "<string>", mode="eval")
>>> ast.dump(node)
"Expression(body=BinOp(left=BinOp(left=Name(id='a', ctx=Load()), op=Add(), right=Constant(value=1, kind=None)), op=Sub(), right=BinOp(left=BinOp(left=Constant(value=2, kind=None), op=Mult(), right=Constant(value=3, kind=None)), op=Div(), right=UnaryOp(op=USub(), operand=Constant(value=4, kind=None)))))"

The top node of our tree is the Expression node which has a single child - the BinOp node (standing for "binary operation") which has two operands in turn and an op attribute standing for "operation".

Here is the pretty-printed AST:

Expression(
    body=BinOp(
        left=BinOp(
            left=Name(id='a', ctx=Load()), 
            op=Add(), 
            right=Constant(value=1, kind=None)), 
        op=Sub(), 
        right=BinOp(
            left=BinOp(
                left=Constant(value=2, kind=None), 
                op=Mult(), 
                right=Constant(value=3, kind=None)), 
            op=Div(), 
            right=UnaryOp(
                op=USub(), 
                operand=Constant(value=4, kind=None)))))

And here is its graphical representation:

Judging by the output, our evaluator will have to support Expression, BinOp, UnaryOp, Name, and Constant node types. In the BinOp node, we'll support Add, Sub, Mult, and Div operations, and in the UnaryOp node, we'll support USub operation.

Let's wrap our parsing code into a new function and prepare to evaluate the AST.

def evaluate_formula(formula: str, vars: Dict[str, Any]) -> float:
    node = ast.parse(formula, "<string>", mode="eval")
    # We'll write eval_node in the next section
    return eval_node(node, vars)

By the end of the post we expect this function to work like this:

>>> evaluate_formula("a * 2 + b / c", {"a": 1, "b": 2, "c": 4})
2.5

The user will supply the formula source code and the application will supply values for the predefined variables.

Evaluation

The eval_node function is going to be the main gateway of our evaluator. It should accept any supported AST node and produce the result. Of course, it's going to treat every node type differently, so we'll make it into a switch redirecting the node to a more specific function.

def eval_node(node: ast.AST, vars: Dict[str, Any]) -> float:
    EVALUATORS = {
        ast.Expression: eval_expression,
        ast.Constant: eval_constant,
        ast.Name: eval_name,
        ast.BinOp: eval_binop,
        ast.UnaryOp: eval_unaryop,
    }

    for ast_type, evaluator in EVALUATORS.items():
        if isinstance(node, ast_type):
            return evaluator(node, vars)

    raise KeyError(node)

Now we have to make an evaluation function for each of the node types.

Expression

def eval_expression(node: ast.Expression, vars: Dict[str, Any]) -> float:
    return eval_node(node.body, vars)

Expressions are simply top-level nodes. They wrap around a more specific node, and so we'll just unwrap them and move on.

Constants and names

def eval_constant(node: ast.Constant, vars: Dict[str, Any]) -> float:
    return node.value


def eval_name(node: ast.Name, vars: Dict[str, Any]) -> float:
    return vars[node.id]

Two of the most simple nodes we have to deal with. The Constant evaluator simply returns the value of the constant, and the Name evaluator returns the value of the variable that the node is referencing.

We'll deal with the undefined variables in the error handling section.

Binary operations

import operator

def eval_binop(node: ast.BinOp, vars: Dict[str, Any]) -> float:
    OPERATIONS = {
        ast.Add: operator.add,
        ast.Sub: operator.sub,
        ast.Mult: operator.mul,
        ast.Div: operator.truediv,
    }

    left_value = eval_node(node.left, vars)
    right_value = eval_node(node.right, vars)
    apply = OPERATIONS[type(node.op)]
    return apply(left_value, right_value)

This function evaluates the left and the right operands using eval_node and then applies the binary operation over their values.

Python's standard operator module contains handy functions for arithmetic operations. These come to be useful in cases like this, but nothing stops you from writing those functions yourself.

Unary operation(s)

def eval_unaryop(node: ast.UnaryOp, vars: Dict[str, Any]) -> float:
    OPERATIONS = {
        ast.USub: operator.neg,
    }

    operand_value = eval_node(node.operand, vars)
    apply = OPERATIONS[type(node.op)]
    return apply(operand_value)

The implementation is almost identical to eval_binop, but this time we only have one operand.

Does it work?

At this point the implementation is already functional:

>>> evaluate_formula("a * 2 + b / c", {"a": 1, "b": 2, "c": 4})
2.5
>>> evaluate_formula("1.5 * (12 - 2)", {})
15.0
>>> evaluate_formula("(points - 100 * bans) / gamesPlayed", {"points": 1200, "bans": 3, "gamesPlayed": 23})
39.130434782608695

But we're not done yet. We have left some loose ends making this proof of concept, so now let's review all the code, add error handling and tighten up security in some parts.

Error handling and security

Exception types

Let's start by defining the exception classes.

Our formula engine will raise two types of exceptions: syntax errors and runtime errors. Syntax errors will let users know if their formula is invalid, and runtime errors will let them know that something went wrong when the formula was calculated. As a good practice, we'll make both exception types inherit from a single base class. We'll also save the line number and the character column into the syntax error so that the user would know where exactly they made a mistake.

class FormulaError(Exception):
    pass


class FormulaSyntaxError(FormulaError):
    def __init__(self, msg: str, lineno: int, offset: int):
        self.msg = msg
        self.lineno = lineno  # 1-based line number
        self.offset = offset  # 1-based character column

    def __str__(self):
        return f"{self.lineno}:{self.offset}: {self.msg}"


class FormulaRuntimeError(FormulaError):
    pass

Now, syntax errors in our engine can come from two places: either from the Python's parser itself (if the source is not valid Python) or from our code (if the source is valid Python but not a valid formula). The first kind will come in the form of SyntaxError exceptions. Let's convert those SyntaxErrors into our FormulaSyntaxErrors. That way we'll hide the implementation details of our evaluator, making the API more consistent.

class FormulaSyntaxError(FormulaError):
    # some code omitted

    @classmethod
    def from_syntax_error(cls, error: SyntaxError, msg: str) -> "FormulaSyntaxError":
        return cls(msg=f"{msg}: {error.msg}", lineno=error.lineno, offset=error.offset)

    # some code omitted

The second kind of syntax errors (coming from our evaluation code) will have to be pointed to a position in the source code too. But where do we get it? Most AST nodes have lineno and col_offset attributes, but there is a catch. col_offset is the byte offset of the error, while SyntaxErrors and our errors use the character offset.

This is important because some characters (specifically, non-ASCII characters) get encoded to multiple bytes in UTF-8. If we use the byte offset as the character offset, our errors may point to the wrong place.

Can we convert byte offset to character offset? Absolutely! With this handy function:

def byte_offset_to_char_offset(source: str, byte_offset: int) -> int:
    while True:
        try:
            # Cut out the bytes before the offset and try to decode it.
            pre_source = source.encode()[:byte_offset].decode()
            break
        except UnicodeDecodeError:
            # Decoding failed, move back 1 byte.
            byte_offset -= 1
            continue
    # Decoding succeeded, count the characters.
    return len(pre_source)

What it does is it cuts out all the bytes before the byte_offset mark and then attempts to count the characters in the cut out part. The cut-out byte sequence may be an invalid UTF-8 string: either if we've accidentally cut in the middle of a multi-byte character, or if the source is already ill-encoded. So we have to handle decoding errors. When they happen, the function simply shifts the byte_offset by 1 byte towards the start. It does so until it finds a valid substring or until it runs out of the string (because an empty byte sequence is a valid UTF-8 string).

We can use this function to convert the AST node's position and use it in the error object:

class FormulaSyntaxError(FormulaError):
    # some code omitted

    @classmethod
    def from_ast_node(cls, source: str, node: ast.AST, msg: str) -> "FormulaSyntaxError":
        offset = byte_offset_to_char_offset(source, node.col_offset)
        # +1 because the node's col_offset is zero-based, 
        # while the error's offset is one-based.
        return cls(msg=msg, lineno=node.lineno, offset=offset + 1)

    # some code omitted

Notice that whenever we want to throw a FormulaSyntaxError in our code, we have to have the formula source on hand. That means we'll have to pass it to all of our evaluation functions as an argument.

Now let's walk through the code we've written so far and tidy it up.

evaluate_formula

MAX_FORMULA_LENGTH = 255

def evaluate_formula(formula: str, vars: Dict[str, Any]) -> float:
    if len(formula) > MAX_FORMULA_LENGTH:
        raise FormulaSyntaxError("The formula is too long", 1, 1)

    try:
        node = ast.parse(formula, "<string>", mode="eval")
    except SyntaxError as e:
        raise FormulaSyntaxError.from_syntax_error(e, "Could not parse")

    try:
        return eval_node(formula, node, vars)
    except FormulaSyntaxError:
        raise
    except Exception as e:
        raise FormulaRuntimeError(f"Evaluation failed: {e}")

• Notice that we restrict the length of the formula. Letting users execute formulas of unlimited length is dangerous. Large formulas can consume a lot of memory, perform complex calculations that take a lot of the CPU time or simply crash the Python's parser with too much nesting.
• When ast.parse throws a SyntaxError, we wrap it into our error type.
• You have to be prepared that the users will always find a way to make your evaluator raise an unexpected exception. Even if the formula is valid, it can still crash on division by zero, for example, and we can't let user mistakes affect our application's flow.
  So we catch all evaluation-time errors. Syntax errors are returned as-is, and all the other errors are wrapped into our defined error type. This way the evaluate_formula function will never raise an error that is not a FormulaError, keeping the calling code safe.

If you test these edits in the shell, you'll see output similar to this:

>>> evaluate_formula("1 + 2 + and", {})
# some lines omitted
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "formulas.py", line 56, in evaluate_formula
    raise FormulaSyntaxError.from_syntax_error(e, "Could not parse")
__main__.FormulaSyntaxError: 1:9: Could not parse: invalid syntax

>>> evaluate_formula("0.0/0.0", {})
# some lines omitted
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "formulas.py", line 63, in evaluate_formula
    raise FormulaRuntimeError(f"Evaluation failed: {e}")
__main__.FormulaRuntimeError: Evaluation failed: float division by zero

eval_node

def eval_node(source: str, node: ast.AST, vars: Dict[str, Any]) -> float:
    EVALUATORS = {
        ast.Expression: eval_expression,
        ast.Constant: eval_constant,
        ast.Name: eval_name,
        ast.BinOp: eval_binop,
        ast.UnaryOp: eval_unaryop,
    }

    for ast_type, evaluator in EVALUATORS.items():
        if isinstance(node, ast_type):
            return evaluator(source, node, vars)

    raise FormulaSyntaxError.from_ast_node(source, node, "This syntax is not supported")

The only change here (besides the new source argument) is more readable syntax errors. Instead of KeyError, we raise FormulaSyntaxError with a position in source and a message:

>>> evaluate_formula("2 * l[1]", {})
# some lines omitted
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  # some lines omitted
  File "formulas.py", line 79, in eval_node
    raise FormulaSyntaxError.from_ast_node(source, node, "This syntax is not supported")
__main__.FormulaSyntaxError: 1:5: This syntax is not supported

eval_constant

def eval_constant(source: str, node: ast.Constant, vars: Dict[str, Any]) -> float:
    if isinstance(node.value, int) or isinstance(node.value, float):
        return float(node.value)
    else:
        raise FormulaSyntaxError.from_ast_node(source, node, "Literals of this type are not supported")

We must restrict supported literal types. The fewer features we support the smaller is the attack surface of the evaluator. If we let strings slide, for example, we'll have to deal with users producing extremely long strings and clogging up the memory: 'a' * 1000000000.

>>> evaluate_formula("'a' + 1000000000", {})
# some lines omitted
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  # some lines omitted
__main__.FormulaSyntaxError: 1:1: Literals of this type are not supported

We also convert all numbers to float. Python's integers are unbounded, which means that their values can grow without limit taking more and more memory. This is usually useful because the developer doesn't have to worry about reaching a limit when working with large numbers. But if a malicious user manages to make a formula that produces large integer numbers, they can consume more memory than you're willing to give. I'll talk about this problem a little more in the "Ideas for extension" section.

Floats don't have this problem because each float always takes up a constant amount of memory. If the value of a float becomes too large or too small, it loses precision but doesn't allocate more memory.

eval_name

def eval_name(source: str, node: ast.Name, vars: Dict[str, Any]) -> float:
    try:
        return float(vars[node.id])
    except KeyError:
        raise FormulaSyntaxError.from_ast_node(source, node, f"Undefined variable: {node.id}")

I promised you we'll deal with the undefined variables:

>>> evaluate_formula("50 + a", {})
# some lines omitted
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  # some lines omitted
__main__.FormulaSyntaxError: 1:6: Undefined variable: a

We also convert all variable values to float too. To make sure no int's slip through from the outside code.

eval_binop and eval_unaryop

def eval_binop(source: str, node: ast.BinOp, vars: Dict[str, Any]) -> float:
    OPERATIONS = {
        ast.Add: operator.add,
        ast.Sub: operator.sub,
        ast.Mult: operator.mul,
        ast.Div: operator.truediv,
    }

    left_value = eval_node(source, node.left, vars)
    right_value = eval_node(source, node.right, vars)

    # This is new
    try:
        apply = OPERATIONS[type(node.op)]
    except KeyError:
        raise FormulaSyntaxError.from_ast_node(source, node, "Operations of this type are not supported")

    return apply(left_value, right_value)


def eval_unaryop(source: str, node: ast.UnaryOp, vars: Dict[str, Any]) -> float:
    OPERATIONS = {
        ast.USub: operator.neg,
    }

    operand_value = eval_node(source, node.operand, vars)

    # This is new
    try:
        apply = OPERATIONS[type(node.op)]
    except KeyError:
        raise FormulaSyntaxError.from_ast_node(source, node, "Operations of this type are not supported")

    return apply(operand_value)

In this version, we handle unsupported operations: when a user tries to raise a number to the power of another number or attempts some other fancy Python operation, the evaluator will fail gracefully.

Complete code

The complete code of this module is available as a GitHub Gist:

An example implementation of a formula evaluator written on top of Python’s AST package.

An example implementation of a formula evaluator written on top of Python’s AST package. - formulas.py

Gist262588213843476

Ideas for extension and more security concerns

All the code in this post comes with no guarantee of its functionality and security. I have tried to make it as safe as I could by applying as many restrictions over user's abilities as I found fit. But you have your own head on your shoulders and you should only rely on yourself when adding a feature that lets users execute arbitrary code server-side.

You have to be especially careful if you're extending this implementation with more features, increasing the attack surface. Nonetheless, I have some ideas about the extension and improvement of the engine.

Validation before evaluation

It would be a good idea to move the validation outside of the evaluation code into a separate function, the same way most programming languages separate compilation and execution.

The validation step (say, a validate_formula function) should accept the formula source and convert it into your own AST type. This type would already be written in a way to only support a subset of Python's syntax, so if the validate_formula returns a node, this node is guaranteed to represent a syntactically valid formula. No syntax errors may be raised after this point.

The next step would be the evaluate_formula function, now accepting AST nodes of your custom pre-validated types. It could be implemented as a method on the node classes as well. This function can only raise runtime errors.

This separation can be used to validate a user's formula without executing it. validate_formula can also accept a list of allowed variable names to warn the user if they make a typo in a variable name or refer to a variable that will not be defined during evaluation.

Supporting value types other than just float

You may allow the use of integers in your evaluator, but you have to be careful with what operations you allow your users to perform. For example, letting users raise large integers to the power of other large integers can produce extremely big numbers.

>>> import sys
>>> sys.getsizeof((100000 ** 10000) ** 1000)
22146212

If you want to support strings, it's a good idea to restrict operations over them too. As I said before, multiplying a string by an integer can produce very long text. These restrictions can take the form of type checking of the operand values in eval_binop and eval_unaryop.

A cool idea would be to support custom predefined functions to allow some non-mathematical or domain-specific operations. Like in Excel or Google Sheets.

A function call parses into a simple Call node:

>>> ast.dump(ast.parse("func(a, b, c)", mode="eval"))
"Expression(body=Call(func=Name(id='func', ctx=Load()), args=[Name(id='a', ctx=Load()), Name(id='b', ctx=Load()), Name(id='c', ctx=Load())], keywords=[]))"

If you're treading this way, make sure that your functions are simple and predictable and they will not consume too many resources on any user input, whatever arguments they are called with, and however many times they are called.

Allowing multiline formulas (i.e. simple scripts)

If you parse formulas in "exec" mode, you can enable users to use statements and write formulas over multiple lines. Complex formulas may be easier to edit with variable assignments:

Backward compatibility issues

The ast package API appears to be somewhat unstable as the language syntax changes from a release to a release. For example, before 3.8 ast.parse returned ast.Num node instead of ast.Constant.

Make sure to thoroughly cover your implementation with tests to detect such issues when you upgrade your project's Python version.

Conclusion

This post serves as an overview of the concept of making a small custom interpreter for the Python syntax for a specific use case. It can hopefully answer the need for a "safe eval" of some readers, but the code here should not be relied upon in security-conscious environments, as it's not peer-reviewed like most popular open-source libraries.

Yet, if you've been using this idea in a production system, I would like to hear if you had any issues with it, here or on oleg@oyam.dev. Thank you!

Cover photo by Michael Heng on Unsplash