Generating GraphQL Queries - An Update

This post is a part of a series of posts related to my Google Summer of Code ‘20 project. It is a follow-up to the last post I wrote about the query generation functionality of the GraphQL add-on for OWASP ZAP.

I mentioned using a TypeDefinitionRegistry for all the GraphQL types last time. Turns out, the graphql-java library also provides a method for creating an unexecutable schema. I refactored the code to reflect this change. This way I was also able to avoid “raw types” warnings.

The next thing I did was to add support for all the remaining types. Because I had the basic code structure in place, the implementation for these was mostly straightforward. I also added unit tests for each type. This is the first time I ever wrote unit tests, and I realised that I was greatly underestimating their practicality. I was able to stay worry-free about not breaking existing functionality when writing newer code or refactoring thanks to them.

Now that the generator was able to cover the entire schema, I added methods that could send a request in either of these three ways,

  • a GET request with the query appended to it in a query string
  • a POST request with a JSON body
  • a POST request with a GraphQL body

I also added methods that could generate queries in different ways,

  • a separate query for each leaf node (scalar or enum) in the schema
  • a separate query for each field under a root type (i.e. a query, mutation, or subscription)
  • a separate query for each root type

What was the point of creating all these extra methods? Well, for one, by breaking up queries into multiple small ones, we would be able to avoid scenarios like,

A Stack Overflow Error

They also allowed me to give the user more freedom to decide how they want to query an endpoint,

The GraphQL Options Panel

With this the GraphQL Query Generation functionality is almost ready. There are still some things that need tweaking, but for now I’m going to be shifting my focus onto Active Scan Input Vectors for GraphQL Queries.




GraphQL: Generating Queries from a Schema

This post is a part of a series of posts related to my Google Summer of Code ‘20 project.

I am currently writing code that allows us to generate queries from a given a GraphQL Schema Definition. This post is a summary of the work I have done until now.

The first thing I did was look for existing open source programs that did this. I found a few, but this was the one that stood out. It gave me the idea of using a recursive function to generate the queries.

Then I followed the ‘Getting Started’ tutorial for graphql-java and set up a very simple endpoint for testing.

What I realised was that we didn’t need an executable schema to generate queries from it. We could do that solely with a TypeDefinitionRegistry. I explored the graphql-java javadoc for a while, and once I had a brief idea of the methods available to me, I decided to write down the logic for the generating function.

Bjarne Stroustrup’s ‘Programming’ is the book I learnt programming from. One advice that I still follow is to “think before you code”. It is necessary to have a clear understanding of the logic of the program you’re creating; to write it in code is the easy part. The words Stroustrup used were “scribbles on the back of an envelope”.

So I did exactly that. I jotted down the logic of the code on paper first and then in pseudocode so my mentors could review it. The basic idea was to pick an object from the schema -> get all its fields as a list -> traverse through this list and check each field to see if it is a scalar -> If it is, simply print its name and move on and -> if it’s an object, send it back through this process.

const int MAX_DEPTH = 100
function queryGenerator(ObjectType object, int depth){
    fieldsList = object.getAllFields()
    for (field in fieldsList){
        if (field is scalar){
            print field name
        } else if (depth < MAX_DEPTH && field is object) {
            print field name
            queryGenerator(field, depth+1)
        }
    }
}

Since then I have added functionality for nullable fields, interfaces and unions. I also had a lot of fun writing the unit tests for this method. I had to create a couple of schemas from which queries could be generated. Each schema had to have something unique about it, so that if a test failed we would know exactly what was causing the problem. If you’re interested, you can find all the code and tests here.

Anyways, I still have to add support for lists, arguments, enums, mutations and subscriptions in order to cover a schema completely. I’ll write another post when all of that is done.

Until next time!




Adventures in Measure Theory - 5

I am following the Measure Theory series by D.H. Fremlin and blogging my notes here.

Continuing from where I left off last time,

111X (e)

Let $X$ be a set, $\mathcal A$ a family of subsets of $X$, and $\Sigma$ the $\sigma$-algebra of subsets of $X$ generated by $\mathcal A$. Suppose that $Y$ is another set and $\phi:Y\to X$ a function. Show that $\{\phi^{-1}[E]:E\in\Sigma\}$ is the $\sigma$-algebra of subsets of $Y$ generated by $\{\phi^{-1}[A]:A\in\mathcal A\}$.

I have a confession to make. This problem had been troubling me for DAYS. It all came down to proving an equality and I was only able to prove one side of it. I eventually had to look up the solution and found one here on StackExchange. Before I start the proof however, there is an interesting comment on the selected answer that I would like to talk about here:

Nate Eldredge said,

The general trick is that if you want to show something (call it $P$) holds for all sets $A$ in a $\sigma$-algebra $\sigma(\mathcal{C})$ generated by a known collection, the obvious approach “let $A \in \sigma(\mathcal{C})$, show $A$ satisfies $P$” is often not helpful, because you don’t know what $A$ might look like. Instead, try considering the collection $\mathcal{B}$ of all sets satisfying $P$. If you can show that $\mathcal{B}$ is a $\sigma$-algebra containing $\mathcal{C}$, you will be done.

One question I had immediately upon reading this was: Why will we be done if we can show that $\mathcal{B}$ is a $\sigma$-algebra containing $\mathcal{C}$? Then I realised, that the $\sigma$-algebra generated by $\mathcal{C}$ is defined as the intersection of the set of all $\sigma$-algebras that contain $\mathcal{C}$, i.e.,

\[\sigma(\mathcal{C}) = \bigcap\{\Sigma :\Sigma\text{ is a }\sigma\text{-algebra and }\mathcal{C}\subseteq\Sigma \}\]

which means that $\mathcal{B}$ is also a part of this intersection, and hence, every element of $\sigma(\mathcal{C})$ must satisfy $P$ because every element of $\mathcal{B}$ satisfies $P$.

I think this is a nice approach. Anyways, let’s get back to the proof,

Proof.
We want to show that $\{\phi^{-1}[E]:E\in\Sigma\}$ is the $\sigma$-algebra of subsets of $Y$ generated by $\{\phi^{-1}[A]:A\in\mathcal A\}$. Or in other words, $\{\phi^{-1}[E]:E\in\Sigma\}$ equals $\bigcap T$ where

\[T = \{\Omega :\Omega\text{ is a }\sigma\text{-algebra of subsets of Y and }\{\phi^{-1}[A]:A\in\mathcal A\}\subseteq\Omega\}\]

First we will show that $\bigcap T\subseteq\{\phi^{-1}[E]:E\in\Sigma\}$.

  • In 111X (d) we proved that $\{\phi^{-1}[E]:E\in\Sigma\}$ is a $\sigma$-algebra of subsets of $Y$ (the domain of $\phi$).
  • $\mathcal A\subseteq\Sigma$
    $\implies\{\phi^{-1}[A]:A\in\mathcal{A}\}\subseteq\{\phi^{-1}[E]:E\in\Sigma\}\}$
    $\implies\{\phi^{-1}[E]:E\in\Sigma\}\in T$
    $\implies\bigcap T\subseteq\{\phi^{-1}[E]:E\in\Sigma\}$

Now we will show that $\{\phi^{-1}[E]:E\in\Sigma\}\subseteq\bigcap T$. For this we will use the new approach we read about above.

Let $\mathcal D$ be a family of subsets of $X$ such that for every $D$ in $\mathcal D$ we have, $\phi^{-1}[D]\in\bigcap T$, i.e.,

\[\mathcal D = \{D: D\subseteq X \text{ and }\phi^{-1}[D]\in\bigcap T \}\]

Now,

(i) We know that $\emptyset\subseteq X$ and $\phi^{-1}[\emptyset]=\emptyset\in\bigcap T$. Thus, $\emptyset\in\mathcal D$.

(ii) Let $D\in\mathcal D$. For every $\phi^{-1}[D]\in\bigcap T$ we have,

\[{ Y\setminus\phi^{-1}[D]\in\bigcap T \\ \implies\phi^{-1}[X\setminus D]\in\bigcap T }\]

Also, it is obvious that $X\setminus D\subseteq X$. Thus, $X\setminus D\in\mathcal D\,\,\forall\,\,D\in\mathcal D$.

(iii) Let $\langle E_n \rangle_{n\in\Bbb N}$ be a sequence of sets in $\mathcal D$. Then $\langle\phi^{-1}[E_n]\rangle_{n\in\Bbb N}\in\bigcap T$. This means that,

\[{ \bigcup_{n\in\Bbb N}\phi^{-1}[E_n]\in\bigcap T \\ \implies\phi^{-1}[\bigcup_{n\in\Bbb N}E_n]\in\bigcap T }\]

Also, $\bigcup_{n\in\Bbb N}E_n\subseteq X$. Thus, $\bigcup_{n\in\Bbb N}E_n\in\mathcal D$.

From (i), (ii) and (iii) it is clear that $\mathcal D$ is a $\sigma$-algebra of subsets of $X$.

(iv) From the definition of $T$,

\[{ \{\phi^{-1}[A]:A\in\mathcal A\}\subseteq\bigcap T \\ \implies\mathcal A\subseteq\mathcal D }\]

Thus, $D$ is a $\sigma$-algebra of subsets of $X$ that contains $\mathcal A$. This means that

\[\Sigma\subseteq\mathcal D\]

and therefore from the definition of $\mathcal D$,

\[\phi^{-1}[E]\in\bigcap T\,\,\forall\,\, E\in\Sigma \\ \implies\{\phi^{-1}[E]: E\in\Sigma \}\subseteq\bigcap T\]

We have thus proved both the sides, $\bigcap T\subseteq\{\phi^{-1}[E]:E\in\Sigma\}$ and $\{\phi^{-1}[E]: E\in\Sigma \}\subseteq\bigcap T$. Therefore, $\{\phi^{-1}[E]: E\in\Sigma \}=\bigcap T$. \(\tag*{$\square$}\)

Phew, that was one troublesome problem. If you have reached the end of this post, I commend your willpower. Let me know if there are any mistakes in my solution, or you know of a more elegant / easier / better proof for this problem. Drop an email at ricekot [at] gmail [dot] com.




Adventures in Measure Theory - 4

I am following the Measure Theory series by D.H. Fremlin and blogging my notes here.

Continuing from where I left off last time,

111X (c)

Let $X$ and $Y$ be sets and $\Sigma$ a $\sigma$-algebra of subsets of $X$. Let $\phi:X\to Y$ be a function. Show that $\{F:F\subseteq Y,\,\phi^{-1}[F]\in\Sigma\}$ where $\phi^{-1}[F] = \{x: x\in X, \phi (x)\in F\}$ is a $\sigma$-algebra of subsets of $Y$.

Let’s try to understand the problem first. Consider a collection $\Sigma_Y$ of subsets of $Y$ such that if we construct a set $S’$ for every set $S$ in $\Sigma_Y$ with the preimages of elements of $S$ under $\phi$ then $S’$ will lie in $\Sigma$. We have to show that $\Sigma_Y$ is a $\sigma$-algebra of subsets of $Y$.

Proof.
Let $\Sigma_Y = \{F:F\subseteq Y,\,\phi^{-1}[F]\in\Sigma\}$.

(i) We know that $\emptyset\subseteq Y$ and $\phi^{-1}[\emptyset] = \emptyset\in\Sigma$. Thus, $\emptyset\in\Sigma_Y$.

(ii) Let $F\in\Sigma_Y$. Then $\phi^{-1}[F]\in\Sigma$ and since $\Sigma$ is a $\sigma$-algebra of subsets of $X$,

\[{ X\setminus\phi^{-1}[F]\in\Sigma \\ \implies\phi^{-1}[Y]\setminus\phi^{-1}[F]\in\Sigma \\ \implies\phi^{-1}[Y\setminus F]\in\Sigma }\]

Also it is obvious that $Y\setminus F\subseteq Y$. Therefore, since $F$ was chosen arbitrarily, we have $Y\setminus F\in\Sigma_Y\,\,\forall\,\,F\in\Sigma_Y$.

(iii) Let $\langle E_n \rangle_{n\in\Bbb N}$ be a sequence in $\Sigma_Y$. Then there exists a sequence $\langle\phi^{-1}[E_n]\rangle_{n\in\Bbb N}$ in $\Sigma$ corresponding to this one. Since $\Sigma$ is a $\sigma$-algebra of subsets of $X$,

\[{ \bigcup_{n\in\Bbb N}\phi^{-1}[E_n]\in\Sigma \\ \implies\phi^{-1}[\bigcup_{n\in\Bbb N}E_n]\in\Sigma }\]

Also since $\langle E_n \rangle_{n\in\Bbb N}\subseteq\mathcal PY$ we must have $\bigcup_{n\in\Bbb N} E_n \subseteq Y$. Therefore, for all sequences $\langle E_n \rangle_{n\in\Bbb N}$ in $\Sigma_Y$ we have $\bigcup_{n\in\Bbb N} E_n \in\Sigma_Y$.

From (i), (ii), and (iii) it is clear that $\Sigma_Y$ is a $\sigma$-algebra of subsets of $Y$. \(\tag*{$\square$}\)

111X (d)

Let $X$ and $Y$ be sets and $T$ a $\sigma$-algebra of subsets of $Y$. Let $\phi:X\to Y$ be a function. Show that $\{\phi^{-1}[F]:F\in T\}$ is a $\sigma$-algebra of subsets of $X$.

This seems like the previous problem, but in reverse. We have to show that the family of sets of preimages of elements in sets in $T$ is a $\sigma$-algebra of subsets of $X$.

Proof.

Let $\Sigma = \{\phi^{-1}[F]:F\in T\}$.

(i) $\phi^{-1}[F]$ is defined as $\{x: x\in X, \phi(x)\in F\}$. Thus, $\phi^{-1}[F]\subseteq X\,\,\forall\,\,F\subseteq Y$.

(ii) Since $T$ is a $\sigma$-algebra, $\emptyset\in T$. Also, $\phi^{-1}[\emptyset] = \emptyset$. Therefore $\emptyset\in\Sigma$.

(iii) We know that for every $F\in T$ we have $Y\setminus F\in T$. This means that for every $\phi^{-1}[S]\in\Sigma$ we also have

\[{ \phi^{-1}[Y\setminus F]\in\Sigma \\ \implies\phi^{-1}[Y]\setminus\phi^{-1}[F]\in\Sigma \\ \implies X\setminus\phi^{-1}[F]\in\Sigma }\]

(iv) Let $\langle E_n \rangle_{n\in\Bbb N}$ be a sequence in $T$. Then $\bigcup_{n\in\Bbb N}E_n\in T$. Thus, for every sequence $\langle \phi^{-1}[E_n] \rangle_{n\in\Bbb N}\in\Sigma$ we also have

\[{ \bigcup_{n\in\Bbb N}\phi^{-1}[E_n]\in\Sigma \\ \implies\phi^{-1}[\bigcup_{n\in\Bbb N}E_n]\in\Sigma }\]

Therefore, from (i), (ii) and (iii) we can conclude that $\Sigma$ is a $\sigma$-algebra of subsets of $X$. \(\tag*{$\square$}\)




Adventures in Measure Theory - 3

I am following the Measure Theory series by D.H. Fremlin and blogging my notes here.

Today we’re going to solve some problems!

111X (a)

The nine pairs are:

  • $E\cap(\bigcup_{n\in\Bbb N}F_n) = \bigcup_{n\in\Bbb N}(E\cap F_n)$
  • $E\cup(\bigcap_{n\in\Bbb N}F_n) = \bigcap_{n\in\Bbb N}(E\cup F_n)$
  • $\bigcup_{n\in\Bbb N}(E_n\setminus F) = (\bigcup_{n\in\Bbb N}E_n)\setminus F$
  • $E\setminus(\bigcup_{n\in\Bbb N}F_n) = \bigcap_{n\in\Bbb N}(E\setminus F_n)$
  • $\bigcup_{n\in\Bbb N}(E\setminus F_n) = E\setminus(\bigcap_{n\in\Bbb N}F_n)$
  • $\bigcap_{n\in\Bbb N}(E_n\setminus F) = (\bigcap_{n\in\Bbb N}E_n)\setminus F$
  • $\bigcap_{m,n\in\Bbb N}(E_m\setminus F_n) = (\bigcap_{n\in\Bbb N}E_n)\setminus(\bigcup_{n\in\Bbb N}F_n)$
  • $(\bigcup_{n\in\Bbb N}E_n)\cap(\bigcup_{n\in\Bbb N}F_n) = \bigcup_{m,n\in\Bbb N}(E_m\cap F_n)$
  • $(\bigcap_{n\in\Bbb N}E_n)\cup(\bigcap_{n\in\Bbb N}F_n) = \bigcap_{m,n\in\Bbb N}(E_m\cup F_n)$

111X (b)

All ‘open intervals’ $(a,b)$, $(-\infty, b)$, $(a, \infty)$ are open sets.

Proof.
Consider an interval $(a,b)$. We want to show that $\forall\,\, x\in (a,b)\,\,\exists\,\,\delta > 0$ such that $(x-\delta,x+\delta)\in (a,b)$. If we set $\delta = \min\{x-a, b-x\}$ we are done.

  • How did we get this value of $\delta$?
    Since $\delta$ will be different for every $x$, we can deduce that it must be a function of $x$. Now we want a value of $\delta$ such that $x - \delta \ge a$ and $x + \delta \le b$. The largest permissible value of $\delta$ will be the minimum of the two values we get when these two inequalities are written as equalities i.e. either $x - \delta = a$ or $x + \delta = b$.
All intervals (bounded or unbounded, open, closed or half-open) are Borel sets.

Proof.
Borel sets are the members of the $\sigma$-algebra of subsets of $\Bbb R$ generated by the open sets of $\Bbb R$. We just proved above that all open intervals (bounded and unbounded) are open sets, and hence are also Borel sets. Now we have to prove that closed and half-open intervals are also Borel sets.

For any open interval $(a, b)$ in a Borel $\sigma$-algebra, it’s complement $(-\infty,a]\cup[b, \infty)$ also lies in the Borel $\sigma$-algebra. Likewise we can construct all possible half-open or closed intervals simply by taking the union, complement or perhaps both of the Borel sets we already have (or get).

There must be a more elegant proof; I am not convinced with the two paragraphs I have whipped up. Based on what I found here on StackExchange, here is a much better proof:

The initial argument remains the same. All open intervals must be Borel sets (by definition). We will now show that closed and half-open intervals can be expressed as open intervals.

Consider the sets $[a, b]$ and $\bigcap_{n\in\Bbb N}(a-\frac{1}{n}, b+\frac{1}{n})$. It is clear that $[a, b] \subseteq (a-\frac{1}{n}, b+\frac{1}{n})\forall n\in\Bbb N$. Thus,

\[[a, b] \subseteq\bigcap_{n\in\Bbb N}(a-\frac{1}{n}, b+\frac{1}{n}) \tag{i}\]

Now, let $x\in\bigcap_{n\in\Bbb N}(a-\frac{1}{n}, b+\frac{1}{n})$. We will prove that $x\in [a, b]$ by contradiction. Let us assume that $x\notin [a, b]$ or more specifically, $x < a$. Then, by the Archimedean property, we can say that $\exists\,\, n\in\Bbb N$ such that $1 < n(a-x)$ or $x < a - \frac{1}{n}$. Similarly, if $x > b$ then $x > b+\frac{1}{n}$ for some $n\in\Bbb N$. These two inequalities are a contradiction because $a-\frac{1}{n} < x < b+\frac{1}{n} \,\,\forall\,\, n\in\Bbb N$. This means that our assumption was wrong and $x\in [a, b]$ indeed. Thus,

\[\bigcap_{n\in\Bbb N}(a-\frac{1}{n}, b+\frac{1}{n})\subseteq [a, b]\tag{ii}\]

From $(i)$ and $(ii)$, we have,

\[[a, b] = \bigcap_{n\in\Bbb N}(a-\frac{1}{n}, b+\frac{1}{n})\]

This means that $[a, b]$ is also an open interval and hence a Borel set.

In a similar fashion we can prove that,

\[(a, b] = \bigcap_{n\in\Bbb N} (a, b + \frac{1}{n}) \\ [a, b) = \bigcap_{n\in\Bbb N} (a - \frac{1}{n}, b)\]

Hence, proved.