GraphQL and security

Imagine you have a web application that allows people view widgets by name. Somewhere deep in your codebase, a programmer has thoughtfully updated the existing ES5 SQL injection to this stylish new ES6 SQL injection:

`select * from widgets where name = '${name}';`

Injection attacks just like this one persist in-spite of the fact that a search for “sql injection tutorial” returns around 3,740,000 results on Google. They have made the top of the OWASP top 10 in 2010 and 2013 and probably will again in 2016 and likely for the foreseeable future. Motherboard even calls it “the hack that will never go away“.

The standard answer to this sort of problem is input sanitization. It’s standard enough that it shows up in jokes.

xkcd’s famous “Exploits of a Mom

But when faced with such consistent failure, it’s reasonable to ask if there isn’t something systemic going on.

There is a sub-field of security research known as Language Theoretic Security (Langsec) that is asking exactly that question.

Exploitation is unexpected computation caused reliably or probabilistically by some crafted inputs. — Meredith Patterson

Dropping the students table in the comic is exactly the kind of “unexpected computation” they are talking about. To combat it, Langsec encourages programmers to consider their inputs as a language and the sum of the adhoc checks on those inputs as a parser for that language.

They advocate a clean separation of concerns between the recognition and processing of inputs, and bringing a recognizer of appropriate strength to bear on the input you are parsing (ie: not validating HTML/XML with a regex)

Where this starts intersecting with GraphQL is in what this actually implies:

This design and programming paradigm begins with a description of valid inputs to a program as a formal language (such as a grammar or a DFA). The purpose of such a disciplined specification is to cleanly separate the input-handling code and processing code.

A LangSec-compliant design properly transforms input-handling code into a recognizer for the input language; this recognizer rejects non-conforming inputs and transforms conforming inputs to structured data (such as an object or a tree structure, ready for type or value-based pattern matching).

The processing code can then access the structured data (but not the raw inputs or parsers’ temporary data artifacts) under a set of assumptions regarding the accepted inputs that are enforced by the recognizer.

If all that starts sounding kind of familiar, well it did to me too.


GraphQL allows you to define a formal language via it’s type system. As queries arrive, they are lexed, parsed, matched against the user defined types and formed into an Abstract Syntax Tree (AST). The contents of that AST are then made available to processing code via resolve functions.

The promise of Langsec is “software free from broad and currently dominant classes of bugs and vulnerabilities related to incorrect parsing and interpretation of messages between software components”, and GraphQL seems poised to put this within reach of every developer.

Turning back to the example we started with, how could we use GraphQL to protect against that SQL injection? Lets get this going in a test.


import expect from 'expect'
import {
} from 'graphql'
import { GraphQLError } from 'graphql/error';
import { Kind } from 'graphql/language';

describe('SQL injection', () => {

  it('returns a SQL injected string', async () => {

    let schema = new GraphQLSchema({
      query: new GraphQLObjectType({
        name: 'Query',
        fields: () => ({
          widgets: {
            type: GraphQLString,
            args: {
              name: {
                description: 'The name of the widget',
                type: new GraphQLNonNull(GraphQLString)
            resolve: (source, {name}) => `select * from widgets where name = '${name}';`

    let query = `
      query widgetByName($name: String!) {
        widgets(name: $name)

    //args: schema, query, rootValue, contextValue, variables
    let result = await graphql(schema, query, null, null, {name: "foo'; drop table widgets; --"})
    expect("select * from widgets where name = 'foo'; drop table widgets; --'")


GraphQL brings lots of benefits (no need for API versioning, all data in a single round trip, etc…), and while those are compelling, simply passing strings into our backend systems misses an opportunity to do something different.

Let’s create a custom type that is more specific than just a “string”; an AlphabeticString.

  it('is fixed with custom types', async () => {

    let AlphabeticString = new GraphQLScalarType({
      name: 'AlphabeticString',
      description: 'represents a string with no special characters.',
      serialize: String,
      parseValue: (value) => {
        if(value.match(/^([A-Za-z]|\s)+$/)) {
          return value
        return null
      parseLiteral: (ast) => {
        if(value.match(/^([A-Za-z]|\s)+$/)) {
          return ast.value
        return null

    let schema = new GraphQLSchema({
      query: new GraphQLObjectType({
        name: 'Query',
        fields: () => ({
          widgets: {
            type: GraphQLString,
            args: {
              name: {
                description: 'The name of the widget',
                type: new GraphQLNonNull(AlphabeticString)
            resolve: (source, {name}) => {
              return `select * from widgets where name = '${name}';`

    let query = `
    query widgetByName($name: AlphabeticString!) {
        widgets(name: $name)

    //args: schema, query, rootValue, contextValue, variables
    let result = await graphql(schema, query, null, null, {name: "foo'; drop table widgets; --"})
    expect(result.errors[0].message).toInclude("got invalid value")

This test now passes; the SQL string is rejected during parsing before ever reaching the resolve function.

On making custom types

There are already libraries out there that provide custom types for things like URLs, datetime’s and other things, but you will definitely want to be able to make your own.

To start defining your own types you will need to understand the role
the various functions play:

    let MyType = new GraphQLScalarType({
      name: 'MyType',
      description: 'this will show up in the documentation!',
      serialize: (value) => { //... }
      parseValue: (value) => { //... },
      parseLiteral: (ast) => { //... }

The serialize function is the easiest to understand: GraphQL responses are serialized to JSON, and if this type needs special treatment before being included in a response, this is the place to do it.

Understanding parseValue and parseLiteral requires a quick look at two different queries:

//name is a string literal, so parseLiteral is called 
query {
  widgets(name: "Soft squishy widget")

//name is a value so parseValue is called
query widgetByName($name: AlphabeticString!) {
  widgets(name: $name)

In the first query, name is a string literal, so your types parseLiteral function will be called. The second query, the name is supplied as the value of a variable so parseValue is called.

Your type could end up being used in either of those scenarios so it’s important to do your validation in both of those functions.

The standard GraphQL types (GraphQLInt, GraphQLFloat, etc.) also implement those same functions.

Putting the whole thing together, the process then looks something like this:

A query arrives, gets tokenized, the parser builds the AST, calling parseValue and parseLiteral as needed. When the AST is complete, it recurses down the AST calling resolve, using parseValue and parseLiteral again on whatever is returned before calling serialize on each to create the response.

Where to go from here

Langsec is a deep topic, with implications wider than just what is discussed here. While GraphQL is certainly not “Langsec in a box”, it not only seems to be making the design patterns that follow from Langsec’s insights a reality, it has a has a shot at making them mainstream. I’d love to see the Langsec lens turned on GraphQL and see how it can guide the evolution of the spec and the practices around it.

I would encourage you to dig into the ideas of Langsec, and the best place to start is here:


A look at the React Lifecycle

Every react component is required to provide a render function. It can return false or it can return elements but it needs to be there. If you providing a single function, it’s assumed to be a render function:

const Foo = ({thing}) => <p>Hello {thing}</p>
<Foo thing="world" />

There has been a fair bit written about the chain of lifecycle methods that React calls leading up to it’s invocation of the render function and afterwards. The basic order is this:


But things are rarely that simple, and often this.setState is called in componentDidMount which gives a call chain that looks like this:


Nesting components inside each other adds another wrinkle to this, as does my use of ES6/7, which adds a few subtle changes to the existing lifecycle methods. To get this sorted out in my own head, I created two classes: an Owner and and Ownee.

class Owner extends React.Component {

  // ES7 Property Initializers replace getInitialState
  //state = {}

  // ES6 class constructor replaces componentWillMount
  constructor(props) {
    console.log("Owner constructor")
    this.state = {
      foo: "baz"

  componentWillReceiveProps(nextProps) {
    console.log("Owner componentWillReceiveProps")

  shouldComponentUpdate(nextProps, nextState) {
    console.log("Owner shouldComponentUpdate")
    return true

  componentWillUpdate(nextProps, nextState) {
    console.log("Owner componentWillUpdate")

  shouldComponentUpdate(nextProps, nextState) {
    console.log("Owner shouldComponentUpdate")
    return true

  render() {
    console.log("Owner render")
    return (
      <div className="owner">
        <Ownee foo={ } />

  componentDidUpdate(nextProps, nextState) {
    console.log("Owner componentDidUpdate")

  componentDidMount() {
    console.log("Owner componentDidMount")

  componentWillUnmount() {
    console.log("Owner componentWillUnmount")


A component is said to be the owner of another component when it sets it’s props. A component whose props are being set is an ownee, so here is our Ownee component:

class Ownee extends React.Component {

  // ES6 class constructor replaces componentWillMount
  constructor(props) {
    console.log("  Ownee constructor")

  componentWillReceiveProps(nextProps) {
    console.log("  Ownee componentWillReceiveProps")

  shouldComponentUpdate(nextProps, nextState) {
    console.log("  Ownee shouldComponentUpdate")
    return true

  componentWillUpdate(nextProps, nextState) {
    console.log("  Ownee componentWillUpdate")

  render() {
    console.log("  Ownee render")
    return (
        <p>Ownee says {}</p>

  componentDidUpdate(nextProps, nextState) {
    console.log("  Ownee componentDidUpdate")

  componentDidMount() {
    console.log("  Ownee componentDidMount")

  componentWillUnmount() {
    console.log("  Ownee componentWillUnmount")


This gives us the following chain:

Owner constructor
Owner render
  Ownee constructor
  Ownee render
  Ownee componentDidMount
Owner componentDidMount

Adding this.setState({foo: "bar"}) into the Owner’s componentDidMount gives us a more complete view of the call chain:

Owner constructor
Owner render
  Ownee constructor
  Ownee render
  Ownee componentDidMount
Owner componentDidMount
Owner shouldComponentUpdate
Owner componentWillUpdate
Owner render
  Ownee componentWillReceiveProps
  Ownee shouldComponentUpdate
  Ownee componentWillUpdate
  Ownee render
  Ownee componentDidUpdate
Owner componentDidUpdate

Things definitely get more complicated when components start talking to each other and passing functions that setState but the basic model is reassuringly straight forward. The changes that ES6/7 bring to the React lifecycle are relatively minor but nonetheless nice to have clear in my head as well.
If you want to explore this further I’ve created a JSbin.

Packaging, pid-files and systemd

When I first built my ArangoDB package one of the problems I had was getting ArangoDB to start after a reboot. While reworking it for Arango 3.0 I ran into this again.
The reason this can be tricky is that ArangoDB, like basically all forking processes needs to write a pid file somewhere. Where things get confusing is that that anything you create in /var/run will be gone next time you reboot leading to errors like this:

-- Unit arangodb.service has begun starting up.
Aug 24 08:50:27 longshot arangod[10366]: {startup} starting up in daemon mode
Aug 24 08:50:27 longshot arangod[10366]: cannot write pid-file '/var/run/arangodb3/'
Aug 24 08:50:27 longshot systemd[1]: arangodb.service: Control process exited, code=exited status=1
Aug 24 08:50:27 longshot systemd[1]: Failed to start ArangoDB.
-- Subject: Unit arangodb.service has failed

If you DuckDuckGo it you can see that people stumble into this pretty regularly.

To understand what’s going on here it’s important to know about what /var/run is actually for.

The Filesystem Hierarchy Standard describes it as a folder for “run-time variable data” and lays out some rules for the folder:

This directory contains system information data describing the system since it was booted. Files under this directory must be cleared (removed or truncated as appropriate) at the beginning of the boot process. Programs may have a subdirectory of /var/run; this is encouraged for programs that use more than one run-time file. Process identifier (PID) files, which were originally placed in /etc , must be placed in /var/run. The naming convention for PID files is .pid. For example, the crond PID file is named /var/run/

Since those words were written in 2004, the evolving needs of init systems, variations across distributions and the idea of storing pid-files (which shouldn’t survive reboot) with logs and stuff (which should) have all conspired to push for the creation of a standard place to put ephemeral data: /run.

Here in 2016, /run is a done deal, and for backwards compatibility, /var/run is now simply a simlink to /run:

mike@longshot ~/$  ls -l /var/
total 52
lrwxrwxrwx  1 root root     11 Sep 30  2015 lock -> ../run/lock
lrwxrwxrwx  1 root root      6 Sep 30  2015 run -> ../run

Looking back at our cannot write pid-file '/var/run/arangodb3/' error, a few things are clear. First, we should probably stop using /var/run since /run has been standard since around 2011.

Second, our files disappear because /run is a tmpfs. While there are some subtleties it’s basically storing your files in RAM.

So the question is; how do we ensure our /run folder is prepped with our /run/arangodb3 directory (and whatever other files) before our systemd unit file is run? As it happens, systemd has a subproject that deals with this: tmpfiles.d.

The well-named tmpfiles.d creates tmpfiles in /run and /tmp (and a few others). It does this by reading conf files written in a simple configuration format out of certain folders. A quick demo:

mike@longshot ~$  sudo bash -c "echo 'd /run/foo 0755 mike users -' > /usr/lib/tmpfiles.d/foo.conf"
mike@longshot ~$  sudo systemd-tmpfiles --create foo.conf
mike@longshot ~$  ls -l /run
drwxr-xr-x  2 mike     users     40 Aug 24 14:18 foo

While we specified an individual conf file by name running systemd-tmpfiles --create would create the files for all the conf files that exist in /usr/lib/tmpfiles.d/.

mike@longshot ~$  ls -l /usr/lib/tmpfiles.d/
total 104
-rw-r--r-- 1 root root   30 Jul  5 10:35 apache.conf
-rw-r--r-- 1 root root   78 May  8 16:35 colord.conf
-rw-r--r-- 1 root root  574 Jul 25 17:10 etc.conf
-rw-r--r-- 1 root root  595 Aug 11 08:04 gvfsd-fuse-tmpfiles.conf
-rw-r--r-- 1 root root  362 Jul 25 17:10 home.conf

Tying all this together is a systemd service that runs just before that uses that exact command to create all the tmpfiles:

mike@longshot ~/$  systemctl cat systemd-tmpfiles-setup.service
# /usr/lib/systemd/system/systemd-tmpfiles-setup.service
#  This file is part of systemd.
#  systemd is free software; you can redistribute it and/or modify it
#  under the terms of the GNU Lesser General Public License as published by
#  the Free Software Foundation; either version 2.1 of the License, or
#  (at your option) any later version.

Description=Create Volatile Files and Directories
Documentation=man:tmpfiles.d(5) man:systemd-tmpfiles(8)
DefaultDependencies=no systemd-sysusers.service

ExecStart=/usr/bin/systemd-tmpfiles --create --remove --boot --exclude-prefix=/dev

If your unit file includes you know that tmpfiles you specified will exist when your unit file is run.

Knowing that this plumbing is in place, your package should include a conf file which gets installed into /usr/lib/tmpfiles.d/. Here is mine for ArangoDB:

mike@longshot ~/projects/arangodb_pkg (master)$  cat arangodb-tmpfile.conf 
d /run/arangodb3 0755 arangodb arangodb -

While this will ensure that tmpfiles are created next time the computer boots, we also need to make sure the service can be started right now. If you are packaging software for ArchLinux that means having a post_install hook that looks like this:

post_install() {
  systemd-tmpfiles --create arangodb.conf

If you are running systemd, and you probably are, this is the way to go. While it’s not hard to find people using mkdir in their unit file’s ExecStartPre section (been there, done that) or writing some sort of startup script, this is much cleaner. Make use of the infrastructure that is there.

D3 and React 3 ways

D3 and React are two of the most popular libraries out there and a fair bit has been written about using them together.
The reason this has been worth writing about is the potential for conflict between them. With D3 adding and removing DOM elements to represent data and React tracking and diffing of DOM elements, either library could end up with elements being deleted out from under it or operations returning unexpected elements (their apparent approach when finding such an element is “kill it with fire“).

One way of avoiding this situation is simply telling a React component not to update it’s children via shouldComponentUpdate(){ return false }. While effective, having React manage all the DOM except for some designated area doesn’t feel like the cleanest solution. A little digging shows that there are some better options out there.

To explore these, I’ve taken D3 creator Mike Bostock’s letter frequency bar chart example and used it as the example for all three cases. I’ve updated it to ES6, D3 version 4 and implemented it as a React component.

Mike Bostock’s letter frequency chart

Option 1: Use Canvas

One nice option is to use HTML5’s canvas element. Draw what you need and let React render the one element into the DOM. Mike Bostock has an example of the letter frequency chart done with canvas. His code can be transplanted into React without much fuss.

class CanvasChart extends React.Component {

  componentDidMount() {
    //All Mike's code

  render() {
    return <canvas width={this.props.width} height={this.props.height} ref={(el) => { this.canvas = el }} />

I’ve created a working demo of the code on Plunkr.
The canvas approach is something to consider if you are drawing or animating a large amount of data. Speed is also in it’s favour, but React probably narrows the speed gap a bit.

A single element is produced since the charts are drawn with Javascript no other elements need be created or destroyed, avoiding the conflict with React entirely.

Option 2: Use react-faux-dom

Oliver Caldwell’s react-faux-dom project creates a Javascript object that passes for a DOM element. D3 can do it’s DOM operations on that and when it’s done you just call toReact() to return React elements. Updating Mike Bostock’s original bar chart demo gives us this:

import React from 'react'
import ReactFauxDOM from 'react-faux-dom'
import d3 from 'd3'

class SVGChart extends React.Component {

  render() {
    let data =

    let margin = {top: 20, right: 20, bottom: 30, left: 40},
      width = this.props.width - margin.left - margin.right,
      height = this.props.height - - margin.bottom;

    let x = d3.scaleBand()
      .rangeRound([0, width])

    let y = d3.scaleLinear()
      .range([height, 0])

    let xAxis = d3.axisBottom()

    let yAxis = d3.axisLeft()
      .ticks(10, "%");

    //Create the element
    const div = new ReactFauxDOM.Element('div')
    //Pass it to and proceed as normal
    let svg ="svg")
      .attr("width", width + margin.left + margin.right)
      .attr("height", height + + margin.bottom)
      .attr("transform", `translate(${margin.left},${})`);

      x.domain( => d.letter));
      y.domain([0, d3.max(data, (d) => d.frequency)]);

      .attr("class", "x axis")
      .attr("transform", `translate(0,${height})`)

      .attr("class", "y axis")
      .attr("transform", "rotate(-90)")
      .attr("y", 6)
      .attr("dy", ".71em")
      .style("text-anchor", "end")

      .attr("class", "bar")
      .attr("x", (d) => x(d.letter))
      .attr("width", 20)
      .attr("y", (d) => y(d.frequency))
      .attr("height", (d) => {return height - y(d.frequency)});

    //DOM manipulations done, convert to React
    return div.toReact()


This approach has a number of advantages, and as Oliver points out, one of the big ones is being able to use this with Server Side Rendering. Another bonus is that existing D3 visualizations hardly need to be modified at all to get them working with React. If you look back at the original bar chart example, you can see that it’s basically the same code.

Option 3: D3 for math, React for DOM

The final option is a full embrace of React, both the idea of components and it’s dominion over the DOM. In this scenario D3 is used strictly for it’s math and formatting functions. Colin Megill put this nicely stating “D3’s core contribution is not its DOM model but the math it brings to the client”.

I’ve re-implemented the letter frequency chart following this approach. D3 is only used to do a few calculations and format numbers. No DOM operations at all. Creating the SVG elements is all done with React by iterating over the data and the arrays generated by D3.

Screenshot from 2016-06-02 09-24-34
My pure React re-implementation of Mike Bostock’s letter frequency bar chart. D3 for math, React for DOM. No cheating.

What I learned from doing this, is that D3 does a lot of work for you, especially when generating axes. You can see in the code there is a fair number of “magic values”, a little +5 here or a -4 there to get everything aligned right. Probably all that stuff can be cleaned up into props like “margin” or “padding”, but it’ll take a few more iterations (and possibly actual reuse of these components) to get that stuff all cleaned up. D3 has already got that stuff figured out.

This approach is a lot of work in the short term, but has some real benefits. First, I like this approach for it’s consistency with the React way of doing things. Second, long term, after good boundaries between components are established you can really see lots of possibilities for reuse. The modular nature of D3 version 4 probably also means this approach will lead to some reduced file sizes since you can be very selective about what functions you include.
If you can see yourself doing a lot of D3 and React in the future, the price paid for this purity would be worth it.

Where to go from here

It’s probably worth pointing out that D3 isn’t a charting library, it’s a generic data visualisation framework. So while the examples above might be useful for showing how to integrate D3 and React, they aren’t trying to suggest that this is a great use of D3 (though it’s not an unreasonable use either). If all you need is a bar chart there are libraries like Chart.js and react-chartjs aimed directly at that.

In my particular case I had and existing D3 visualization, and react-faux-dom was the option I used. It’s a perfect balance between purity and pragmatism and probably the right choice for most cases.

Hopefully this will save people some digging.

Graph migrations

One of the things that is not obvious at first glance is how “broad” ArangoDB is. By combining the flexibility of the document model with the joins of the graph model, ArangoDB has become a viable replacement for Postgres or MySQL, which is exactly how I have been using it; for the last two years it’s been my only database.

One of the things that falls out of that type of usage is a need to actually change the structure of your graph. In a graph, structure comes from the edges that connect your vertices. Since both the vertices and edges are just documents, that structure is actually just more data. Changing your graph structure essentially means refactoring your data.

There are definitely patterns that appear in that refactoring, and over the last little while I have been playing with putting the obvious ones into a library called graph_migrations. This is work in progress but there are some useful functions working already and could use some proper documentation.


One of the first of these is what I have called eagerDelete. If you were wanting to delete Bob from graph below, Charlie and Dave would be orphaned.

Screenshot from 2016-04-06 10-55-54

Deleting Bob with eagerDelete means that Bob is deleted as well as any neighbors whose only neighbor is Bob.

gm = new GraphMigration("test") //use the database named "test"
gm.eagerDelete({name: "Bob"}, "knows_graph")



Occasionally you will end up with duplicate vertices, which should be merged together. Below you can see we have an extra Charlie vertex.


gm = new GraphMigration("test")
gm.mergeVertices({name: "CHARLIE"},{name: "Charlie"}, "knows_graph")



One of the other common transformations is needing to make a vertex out of attribute. This process of “promoting” something to be a vertex is sometimes called reifying. Lets say Eve and Charlie are programmers.


Lets add an attribute called job to both Eve and Charlie identifying them as programmers:


But lets say that we decide that it makes more sense for job: "programmer" to be a vertex on it’s own (we want to reify it). We can use the attributeToVertex function for that, but because Arango allows us to split our edge collections and it’s good practice to do that, lets add a new edge collection to our “knows_graph” to store the edges that will be created when we reify this attribute.


With that we can run attributeToVertex, telling it the attribute(s) to look for, the graph (knows_graph) to search and the collection to save the edges in (works_as).

gm = new GraphMigration("test")
gm.attributeToVertex({job: "programmer"}, "knows_graph", "works_as", {direction: "inbound"})

The result is this:



Another common transformation is exactly the reverse of what we just did; folding the job: "programmer" vertex into the vertices connected to it.

gm = new GraphMigration("test")
gm.vertexToAttribute({job: "programmer"}, "knows_graph", {direction: "inbound"})

That code puts us right back to where we started, with Eve and Charlie both having a job: "programmer" attribute.



There are times when things are just not connected the way you want. Lets say in our knows_graph we want all the inbound edges pointing at Bob to point instead to Charlie.

We can use redirectEdges to do exactly that.

gm = new GraphMigration("test")
gm.redirectEdges({_id: "persons/bob"}, {_id: "persons/charlie"}, "knows_graph", {direction: "inbound"})

And now Eve and Alice know Charlie.


Where to go from here.

As the name “graph migrations” suggests the thinking behind this was to create something similar to the Active Record Migrations library from Ruby on Rails but for graphs.

As more and more of this goes from idea to code and I get a chance to play with it, I’m less sure that a direct copy of Migrations makes sense. Graphs are actually pretty fine-grained data in the end and maybe something more interactive makes sense. It could be that this makes more sense as a Foxx app or perhaps part of Arangojs or ArangoDB’s admin interface. It feels a little to early to tell.

Beyond providing a little documentation the hope here is make this a little more visible to people who are thinking along the same lines and might be interested in contributing.

Back up your data, give it a try and tell me what you think.

That stonewalling thing

There is a meme in the current crypto “debate” that makes me cringe whenever I read it: the idea of “stonewalling”. It’s come up in the Apple vs FBI case as the ForbesLA Times, Jacobin magazine and others all described Apple as “stonewalling” the FBI.

Wired’s recent Whatsapp story mentioned that “WhatsApp is, in practice, stonewalling the federal government” and while Foreign Policy magazine avoided the word, they captured the essence when they described Whatsapp as a “a service willing to adopt technological solutions to prevent compliance with many types of court orders”.

All of these articles make it sound like Apple/Whatsapp has the data, but it unwilling to give it to the government.

                                                                ]�?c�,��y�l?��3�lF�'���ǘ��IA��O�Y�i�����ё�R��`�[�]�H���P�1'��������S����~tF\�������^��f@��<P�g�	!X���6eh�U�rN���=d@܉eQe���B�lk����\ҠcE��
�$�d&���_xor�s�-���l,v���44�E����n�[���1YL�o�ޜ�g�m�����Tx�f	܁�����å+e�LR�E1���ޅx
                                                                                              �a*�Զ\l�ϫ)4&���or�-�4���C���q��|-2[͘7 ��


Blobs of encrypted text like the one above are useless for anyone put the holder of the decryption key. Where the company holds the decryption key and refused to give it up, it seems reasonable to call that “stonewalling”.

Without the decryption key, you may be in possession of such a blob but you can’t meaningfully be described as “having” the data within it. Calls of “stonewalling” in cases like that are either grandstanding or reveal an opinion-disqualifying level of ignorance.

These accusations of stonewalling obscure what I think is the real appeal of encryption and tools such as Tor: it’s not that these technologies prevent compliance, it’s that companies can prevent the collection certain types of data in the first place.

The authors of a recent paper called “Cryptopolitik and the Darknet” did exactly that when they crawled the darknet for data:

“In order to avoid illegal material, such as media files of child pornography or publications by terrorist organisations, only textual content was harvested automatically. Any other material was either filtered out or immediately discarded.”

Nobody would think to accuse them of stonewalling or adopting “technological solutions to prevent compliance” for finding a way to do their darknet crawl without accumulating a bunch of data that is going to bring with it complicated law enforcement dealings.

When Whatapp wants to “avoid illegal material” while still remaining in the messaging business, they do it with end-to-end encryption.


Why end-to-end? In end-to-end encryption, the end users hold the decryption keys. Companies who decide to keep the keys themselves become a target of every spy agency on the planet and run the risk of becoming the next Gemalto.

That technologies and architectural choices exist which allow you to filter the data you are exposed to, and therefore your level of legal liability/obligation feels new. Or maybe what’s new is companies willingness to actually implement them.

No-one is interested in obstructing investigations, just managing risk and legal exposure. “If you collect it, they will come” is becoming a common phrase among programmers and security people, and for companies who don’t want to end up holding data related to a crime, painting a giant target on themselves, dedicating resources to servicing government requests, or having awkward public relations moments, end-to-end encryption starts to look like good risk management. Doubly so when you are dealing with multiple governments.

In that context, governments pushing back against end-to-end seem to indicate an existing idea that companies are somehow obligated to collect data on behalf of the government and that using encryption to limit your collection is not OK. This is visible in the issue of the government conscripting companies to do it’s work raised by the FBI’s recent use of the 1789 All-Writs Act law to try to force Apple to build software to hack it’s own phone.

With many years of enthusiastic support from companies like AT&T it’s easy to see where that idea might have come from. As the American government oscillates between attacking tech companies and asking them to do it’s job, and authoritarian governments and international customers look on, it’s not hard to see why many tech companies are far less enthusiastic about facilitating government aims. So far “stonewalling” seems to be a deliberately provocative framing for the “we’ve stopped collecting that data, leave us out of this” reality that end-to-end encryption creates.

Seeing that kind of inflammatory rhetoric from the FBI or congress is one thing, but it’s widespread use by journalists is very disconcerting.

As cries of “stonewalling” turn to accusations of tech companies thinking they are “above the law” and now draft anti-encryption legislation, it’s probably good to remember that blob of encrypted text. It’s not that these companies are getting in the way of the FBI getting data, they are trying to get themselves out of the way by removing their own access to it.

Of all people, former NSA director Michael Hayden recently observed “America is simply more secure with unbreakable end-to-end encryption”. I never thought I would be hoping more people would listen to him.

Graph traversals in ArangoDB

ArangoDB’s AQL query language was created to offer a unified interface for working with key/value, document and graph data. While AQL has been easy to work with and learn, it wasn’t until the addition of AQL traversals in ArangoDB 2.8 that it really felt like it has achieved it’s goal.

Adding keywords GRAPH, OUTBOUND, INBOUND and ANY suddenly made iteration using a FOR loop the central idea in the language. This one construct can now be used to iterate over everything; collections, graphs or documents:

//FOR loops for everything
FOR person IN persons //collections
  FOR friend IN OUTBOUND person GRAPH "knows_graph" //graphs
    FOR value in VALUES(friend, true) //documents

AQL has always felt more like programming than SQL ever did, but the central role of the FOR loop gives a clarity and simplicity that makes AQL very nice to work with. While this is a great addition to the language, it does however, mean that there are now 4 different ways to traverse a graph in AQL and a few things are worth pointing out about the differences between them.

AQL Traversals

There are two variations of the AQL traversal syntax; the named graph and the anonymous graph. The named graph version uses the GRAPH keyword and a string indicating the name of an existing graph. With the anonymous syntax you can simply supply the edge collections

//Passing the name of a named graph
FOR vertex IN OUTBOUND "persons/eve" GRAPH "knows_graph"
//Pass an edge collection to use an anonymous graph
FOR vertex IN OUTBOUND "persons/eve" knows

Both of these will return the same result. The traversal of the named graph uses the vertex and edge collections specified in the graph definition, while the anonymous graph uses the vertex collection names from the _to/_from attributes of each edge to determine the vertex collections.

If you want access to the edge or the entire path all you need to do is ask:

FOR vertex IN OUTBOUND "persons/eve" knows
FOR vertex, edge IN OUTBOUND "persons/eve" knows
FOR vertex, edge, path IN OUTBOUND "persons/eve" knows

The vertex, edge and path variables can be combined and filtered on to do some complex stuff. The Arango docs show a great example:

FOR v, e, p IN 1..5 OUTBOUND 'circles/A' GRAPH 'traversalGraph'
  FILTER p.edges[0].theTruth == true
  AND p.edges[1].theFalse == false
  FILTER p.vertices[1]._key == "G"


Arango can end up doing a lot of work to fill in those FOR v, e, p IN variables. ArangoDB is really fast, so to show the effect these variables can have, I created the most inefficient query I could think of; a directionless traversal across a high degree vertex with no indexes.

The basic setup looked like this except with 10000 vertices instead of 10. The test was getting from start across the middle vertex to end.

Screenshot from 2016-04-05 10-07-04

What you can see is that adding those variables comes at a cost, so only declare ones you actually need.

Traversing a supernode with 10000 incident edges with various traversal methods. N=5. No indexes used.

GRAPH_* functions and TRAVERSAL

ArangoDB also has a series of “Named Operations” that feature among
them a few that also do traversals. There is also a super old-school TRAVERSAL function hiding in the “Other” section. What’s interesting is how different their performance can be while still returning the same results.

I tested all of the traversal functions on the same supernode described above. These are the queries:

//AQL traversal
FOR v IN 2 ANY "vertices/1" edges
  FILTER == "end"
    RETURN v

RETURN GRAPH_NEIGHBORS("db_10000", {_id: "vertices/1"}, {direction: "any", maxDepth:2, includeData: true, neighborExamples: [{name: "end"}]})

RETURN GRAPH_TRAVERSAL("db_10000", {_id:"vertices/1"}, "any", {maxDepth:2, includeData: true, filterVertices: [{name: "end"}], vertexFilterMethod: ["exclude"]})

RETURN TRAVERSAL(vertices, edges, {_id: "vertices/1"}, "any", {maxDepth:2, includeData: true, filterVertices: [{name: "end"}], vertexFilterMethod: ["exclude"]})

All of these returned the same vertex, just with varying levels of nesting within various arrays. Removing the nesting did not make a signficant difference in the execution time.

Traversing a supernode with 10000 incident edges with various traversal methods. N=5.


While TRAVERSAL and GRAPH_TRAVERSAL were not stellar performers here, the both have a lot to offer in terms of customizability. For ordering, depthfirst searches and custom expanders and visitors, this is the place to look. As you explore the options, I’m sure these get much faster.

Slightly less obvious but still worth pointing out that where AQL traversals require an id (“vertices/1000” or a document with and _id attribute), GRAPH_* functions just accept an example like {foo: “bar”} (I’ve passed in {_id: “vertices/1”} as the example just to keep things comparable). Being able to find things, without needing to know a specific id, or what collection to look in is very useful. It lets you abstract away document level concerns like collections and operate on a higher “graph” level so you can avoid hardcoding collections into your queries.

What it all means

The difference between these, at least superficially, similar traversals are pretty surprising. While some where faster than others, none of the options for tightening the scope of the traversal were used (edge restrictions, indexes, directionality). That tells you there is likely a lot of headroom for performance gains for all of the different methods.

The conceptual clarity that AQL traversals bring to the language as a whole is really nice, but it’s clear there is some optimization work to be done before I go and rewrite all my queries.

Where I have used the new AQL traversal syntax, I’m also going to have to check to make sure there are no unused v,e,p variables hiding in my queries. Where you need to use them, it looks like restricting yourself to v,e is the way to go. Generating those full paths is costly. If you use them, make sure it’s worth it.

Slowing Arango down is surprisingly instructive, but with 3.0 bringing the switch to Velocypack for JSON serialization, new indexes, and more, it looks like it’s going to get harder to do. :)