Building a SQL-like language to filter flows

Vincent Bernat

Akvo­rado col­lects net­work flows us­ing IPFIX or sFlow. It stores them in a Click­House data­base. A web con­sole al­lows a user to query the data and plot some graphs. A nice as­pect of this con­sole is how we can fil­ter flows with a SQL-like language:

Filter editor in Akvorado console

Of­ten, web in­ter­faces ex­pose a query builder to build such fil­ters. I think com­bin­ing a SQL-like lan­guage with an ed­i­tor sup­port­ing com­ple­tion, syn­tax high­light­ing, and lint­ing is a bet­ter ap­proach.1

The lan­guage parser is built with pi­geon (Go) from a pars­ing ex­pres­sion gram­mar—or PEG. The ed­i­tor com­po­nent is CodeMirror (Type­Script).

Language parser#

PEG gram­mars are rel­a­tively re­cent2 and are an al­ter­na­tive to con­text-free gram­mars. They are eas­ier to write and they can gen­er­ate bet­ter er­ror mes­sages. Python switched from an LL(1)-based parser to a PEG-based parser in Python 3.9.

pi­geon gen­er­ates a parser for Go. A gram­mar is a set of rules. Each rule is an iden­ti­fier, with an op­tional user-friendly la­bel for er­ror mes­sages, an ex­pres­sion, and an ac­tion in Go to be ex­e­cuted on match. You can find the com­plete gram­mar in parser.​peg. Here is a sim­pli­fied rule:

ConditionIPExpr "condition on IP" ←
  column:("ExporterAddress"i { return "ExporterAddress", nil }
        / "SrcAddr"i { return "SrcAddr", nil }
        / "DstAddr"i { return "DstAddr", nil }) _ 
  operator:("=" / "!=") _ 
  ip:IP {
    return fmt.Sprintf("%s %s IPv6StringToNum(%s)",
      toString(column), toString(operator), quote(ip)), nil
  }

The rule iden­ti­fier is ConditionIPExpr. It case-in­sen­si­tively matches ExporterAddress, SrcAddr, or DstAddr. For each of them, it re­turns the col­umn name with the proper case. That’s what is stored in the column vari­able. Then, it matches one of the pos­si­ble op­er­a­tors. As there is no code block, it stores the matched string di­rectly in the operator vari­able. Then, it tries to match the IP rule, which is de­fined else­where in the gram­mar. If it suc­ceeds, it stores the re­sult of the match in the ip vari­able and ex­e­cutes the fi­nal ac­tion. The ac­tion turns the col­umn, op­er­a­tor, and IP into a proper ex­pres­sion for Click­House. For ex­am­ple, if we have ExporterAddress = 203.0.113.15, we get ExporterAddress = IPv6StringToNum('203.0.113.15').

The IP rule uses a rudi­men­tary reg­u­lar ex­pres­sion but checks if the matched ad­dress is cor­rect in the ac­tion block, thanks to netip.​ParseAddr():

IP "IP address" ← [0-9A-Fa-f:.]+ {
  ip, err := netip.ParseAddr(string(c.text))
  if err != nil {
    return "", errors.New("expecting an IP address")
  }
  return ip.String(), nil
}

Our parser safely turns the fil­ter into a WHERE clause ac­cepted by ClickHouse:3

WHERE InIfBoundary = 'external' 
AND ExporterRegion = 'france' 
AND InIfConnectivity = 'transit' 
AND SrcAS = 15169 
AND DstAddr BETWEEN toIPv6('2a01:e0f:ffff::') 
                AND toIPv6('2a01:e0f:ffff:ffff:ffff:ffff:ffff:ffff')

Integration in CodeMirror#

CodeMirror is a ver­sa­tile code ed­i­tor that can be eas­ily in­te­grated into Java­Script projects. In Akvo­rado, the Vue.js com­po­nent, InputFilter, uses CodeMirror as its foun­da­tion and lever­ages fea­tures such as syn­tax high­light­ing, lint­ing, and com­ple­tion. The source code for these ca­pa­bil­i­ties can be found in the codemirror/​lang-filter/ di­rectory.

Syntax highlighting#

The PEG gram­mar for Go can­not be uti­lized di­rectly4 and the re­quire­ments for parsers for ed­i­tors are dis­tinct: they should be er­ror-tol­er­ant and op­er­ate in­cre­men­tally, as code is typ­i­cally up­dated char­ac­ter by char­ac­ter. CodeMirror of­fers a so­lu­tion through its own parser gen­er­a­tor, Lezer.

We don’t need this ad­di­tional parser to fully un­der­stand the fil­ter lan­guage. Only the ba­sic struc­ture is needed: col­umn names, com­par­i­son and logic op­er­a­tors, quoted and un­quoted val­ues. The gram­mar is there­fore quite short and does not need to be up­dated often:

@top Filter {
  expression
}

expression {
 Not expression |
 "(" expression ")" |
 "(" expression ")" And expression |
 "(" expression ")" Or expression |
 comparisonExpression And expression |
 comparisonExpression Or expression |
 comparisonExpression
}
comparisonExpression {
 Column Operator Value
}

Value {
  String | Literal | ValueLParen ListOfValues ValueRParen
}
ListOfValues {
  ListOfValues ValueComma (String | Literal) |
  String | Literal
}

// […]
@tokens {
  // […]
  Column { std.asciiLetter (std.asciiLetter|std.digit)* }
  Operator { $[a-zA-Z!=><]+ }

  String {
    '"' (![\\\n"] | "\\" _)* '"'? |
    "'" (![\\\n'] | "\\" _)* "'"?
  }
  Literal { (std.digit | std.asciiLetter | $[.:/])+ }
  // […]
}

The ex­pres­sion SrcAS = 12322 AND (DstAS = 1299 OR SrcAS = 29447) is parsed to:

Filter(Column, Operator, Value(Literal),
  And, Column, Operator, Value(Literal),
  Or, Column, Operator, Value(Literal))

The last step is to teach CodeMirror how to map each to­ken to a high­lighting tag:

export const FilterLanguage = LRLanguage.define({
  parser: parser.configure({
    props: [
      styleTags({
        Column: t.propertyName,
        String: t.string,
        Literal: t.literal,
        LineComment: t.lineComment,
        BlockComment: t.blockComment,
        Or: t.logicOperator,
        And: t.logicOperator,
        Not: t.logicOperator,
        Operator: t.compareOperator,
        "( )": t.paren,
      }),
    ],
  }),
});

Linting#

We off­load lint­ing to the orig­i­nal parser in Go. The /api/​v0/​console/​filter/​validate end­point ac­cepts a fil­ter and re­turns a JSON struc­ture with the er­rors that were found:

{
  "message": "at line 1, position 12: string literal not terminated",
  "errors": [{
    "line":    1,
    "column":  12,
    "offset":  11,
    "message": "string literal not terminated",
  }]
}

The lin­ter source for CodeMirror queries the API and turns each er­ror into a di­agnostic.

Completion#

The com­ple­tion sys­tem takes a hy­brid ap­proach. It splits the work be­tween the fron­tend and the back­end to of­fer use­ful sug­ges­tions for com­plet­ing filters.

The fron­tend uses the parser built with Lezer to de­ter­mine the con­text of the com­ple­tion: do we com­plete a col­umn name, an op­er­a­tor, or a value? It also ex­tracts the col­umn name if we are com­plet­ing some­thing else. It for­wards the re­sult to the back­end through the /api/​v0/​console/​filter/​complete end­point. Walk­ing the syn­tax tree was not as easy as I thought, but unit tests helped a lot.

The back­end uses the parser gen­er­ated by pi­geon to com­plete a col­umn name or a com­par­i­son op­er­a­tor. For val­ues, the com­ple­tions are ei­ther static or ex­tracted from the Click­House data­base. A user can com­plete an AS num­ber from an or­ga­ni­za­tion name thanks to the fol­low­ing snippet:

results := []struct {
  Label  string `ch:"label"`
  Detail string `ch:"detail"`
}{}
columnName := "DstAS"
sqlQuery := fmt.Sprintf(`
 SELECT concat('AS', toString(%s)) AS label, dictGet('asns', 'name', %s) AS detail
 FROM flows
 WHERE TimeReceived > date_sub(minute, 1, now())
 AND detail != ''
 AND positionCaseInsensitive(detail, $1) >= 1
 GROUP BY label, detail
 ORDER BY COUNT(*) DESC
 LIMIT 20
`, columnName, columnName)
if err := conn.Select(ctx, &results, sqlQuery, input.Prefix); err != nil {
  c.r.Err(err).Msg("unable to query database")
  break
}
for _, result := range results {
  completions = append(completions, filterCompletion{
    Label:  result.Label,
    Detail: result.Detail,
    Quoted: false,
  })
}

In my opin­ion, the com­ple­tion sys­tem is a ma­jor fac­tor in mak­ing the field ed­i­tor an ef­fi­cient way to se­lect flows. While a query builder may have been more be­gin­ner-friendly, the com­ple­tion sys­tem’s ease of use and func­tion­al­ity make it more en­joy­able to use once you be­come familiar.