Writing Mandelbrot Fractals with Hooks and Forks

Written by Pete Corey on Apr 16, 2018.

We recently saw that through the power of hooks and forks, we could read J expressions just like we’d read an English sentence. But the expressive power of hooks and forks doesn’t end there. We can also write J expressions just like we’d speak them!

Let’s take a minute to refresh ourselves on how J’s hooks and forks work, and then see how we can use them to write some truly grammatical code.

Forks and Hooks

If you think back to our last conversation about J, you’ll remember that we defined the mean verb to be a fork composed of three separate verbs: “sum” (+/), “divided by” (%), and “tally” (#).

All together, these three verbs form a fork that calculates the average of any list passed into it:

   mean =: +/ % #
   mean 1 2 3 4

When passed a single argument, the fork will apply that argument to each of the outer verbs monadically (passing them a single argument), and dyadically apply (passing two arguments) those results to the middle verb.

If you squint your eyes enough, this might start looking like a fork.

Similarly, we can create a hook by composing any two verbs together. For example, we can write an append_mean verb that forms a hook out of the “append” (,) verb and our new mean verb:

   append_mean =: , mean

When passed a single argument, the fork monadically applies that argument to the right-hand verb, and dyadically applies the original argument and the result of the first verb to the left-hand argument.

Unfortunately no amount of squinting will make this look like a real-life hook.

The inner workings of J’s hooks and forks may seem a little complicated, but that low-level obfuscation leads to higher levels of clarity. Namely, we can read our hooks and forks like English sentences!

Writing with Hooks and Forks

Not only do hooks and forks allow us to read our J expressions like English sentences, they also let us write our expressions like we’d write English sentences!

Let’s consider an example.

Imagine we want to construct the Mandelbrot set using J. To test whether a complex number belongs to the set, we repeatedly apply an iterative function to it. If the result of that function ever diverges to infinity (or exceeds a magnitude of two), the point does not belong to the set. If the number hasn’t diverged after some number of iterations, we can assume that it belongs to the set.

The Mandelbrot set equation.

In terms of implementing this in J, it sounds like our best bet will be to store the result of each iteration in an array of complex numbers. The first element in the array will be the point under test (skipping z₀ for convenience), and the last element will be the result of the last application of our iteration function. With that in mind, we can write a verb that computes our next iteration, given our list of z values.

   next =: {. + *:@:{:

This expression is saying that next “is” (=:) the “first element of the array” ({.) “plus” (+) the “square of the last element of the array” (*:@:{:). That last verb combines the “square” (*:) and “last” ({:) verbs together with the “at” (@:) adverb.

You’ll notice that next is a fork. The argument application rules follow the structure we discussed above, but we’re able to read and write the expression linearly from left to write.

While we’re able to compute the next iteration of our Mandelbrot set equation, we still need to append the result back onto our list of z values. In plain English, we want to “append” (,) the “next” (next) value:

   append_next =: , next

Just like our earlier example, append_next is a hook.

We can repeatedly apply our append_next verb to some initial value:

   append_next append_next append_next 0.2j0.2
0.2j0.2 0.2j0.28 0.1616j0.312 0.128771j0.300838

Or we can do that more concisely with the “power” (^:) verb:

   (append_next^:3) 0.2j0.2
0.2j0.2 0.2j0.28 0.1616j0.312 0.128771j0.300838


Final Touches

As a final piece of magic to top off this exploration into J, let’s apply our apply_next verb repeatedly over a grid of complex numbers:

   axis =: 0.005 * 250 - (i.501)
   grid =: (*&0j1 +/ |.) axis
   mbrot =: (append_next^:40)"0 (grid - 0.6)

We’re left with a three dimensional array of complex numbers in our mbrot noun, representing the values of z resulting from repeatedly applying our append_next function to each point in our grid of complex numbers.

As we mentioned earlier, if any of these values of z exceed a magnitude of 2, we can assume they diverge and aren’t a part of the Mandelbrot set.

We can compute that divergence test and render the resulting using viewmat:

   viewmat <&2 | ({:"1 mbrot)

And we’re left with a pretty picture of the Mandelbrot set!

Final Thoughts

It’s no joke that J can be an intimidating language to work with. I’m still trying to lift myself over the initial learning curve, and some of the expressions written above still take some concentration on my part to grok their meaning (even though I wrote them).

That said, there are some incredibly unique and interesting ideas baked into this language, and I’m getting a lot out of the learning experience.

Hex Dumping with Elixir

Written by Pete Corey on Apr 9, 2018.

I recently written about my explorations into the Bitcoin peer-to-peer network from the context of an Elixir application. These explorations have caused me to get up-close and personal with binary data as I serialize and parse packets at the byte level.

Being a visual person, I wanted some way of inspecting the binaries I was constructing and sending. I decided that a hex dump would be the best way to visualize these packets.

What followed was an odyssey of finding and implementing a safe and fast process for printing hex dumps of arbitrary, untrusted binary data from within an Elixir application.

Calling Out to the System

My first instinct for implementing a hex dump method within my application was to not implement it at all! It made more sense to leverage the existing hexdump command line utility living on my system.

Specially, I wanted to render my packets with the hexdump -C command. The -C flag includes an ASCII rendering of the bytes being dumped:

0000   F9 BE B4 D9 76 65 72 73  69 6F 6E 00 00 00 00 00   ....version.....
0010   55 00 00 00 9C 7C 00 00  01 00 00 00 00 00 00 00   U....|..........
0020   E6 15 10 4D 00 00 00 00  01 00 00 00 00            ...M.........

Unfortunately, calling hexdump from within an Elixir application proved to be more challenging than I first expected.

When trying to call system commands, I reflexively reach for Elixir’s System.cmd/3 function. Unfortunately, hexdump relies on the input bytes through either stdin, or through a file. Because System.cmd/3 only lets you pass arguments to your system command, not data through stdin, we can’t use it to build our hex dumps.

Another option would be to write our packets to a temporary file, and use System.cmd/3 to instruct hexdump to load and dump the bytes in that file. Relying on temporary files seems like a poor choice for a logging utility that would be called hundreds to thousands of times per minute.

While System.cmd/3 won’t work, maybe we can use an Elixir Port directly. Unfortunately, while we can pipe our binary data directly to hexdump using a port, there is no way to signal the end of our data by sending the expected EOF (^D) signal. Without signaling the end of our byte stream, closing the port will leave us without any data to show for our work.

Here Be Dragons

Our third option for solving this problem is to dig deeper into our tool belt and pull out the big guns. Both System.cmd/3 and Port have limitations in this context, but Erlang’s :os.cmd/1 gives us exactly what we need:

output =
  ('echo "' ++ :binary.bin_to_list(data) ++ '" | hexdump -C')
  |> :os.cmd()

We can use :os.cmd/1 to evaulate any shell command, including compositions of commands strung together with pipes and redirections.

In this case, our command uses echo to pipe our binary into hexdump -C. The :os.cmd/1 function expects our shell command to be in the form of a character list, so we use Erlang’s :binary.bin_to_list/1 to inject our binary data directly into our echo argument.

However, this solution has major security issues.

Depending on the source of our data binary, we’re potentially giving outside sources free reign to run any shell command on our machine. Considering that this hex dump is intended to log packets received from external sources on the Bitcoin peer-to-peer network, this is a catastrophically bad idea.

We need to find another solution.

Going the Safe Route

Ultimately, I decided that the safest and fastest solution to my problem was to simply build my own hex dump utility in pure Elixir.

The general idea behind the hexdump tool is simple. For every line, display the current byte count in hex, followed by two chunks of eight bytes rendered in hex, followed by all sixteen bytes rendered together as ASCII characters.

This is a great chance to flex our Elixir muscles. Let’s implement this in a to_string/1 function within a new Hexdump module:

defmodule Hexdump do
  def to_string(data) when is_binary(data) do
    # TODO: Implement `to_string`...
  def to_string(data), do: Kernel.inspect(data)

We only want to run our hex dump algorithm on binary data, so we’ll guard our first function head with an is_binary guard. If data isn’t binary, we’ll simply return the result of Kernel.inspect/2.

In order to work more easily with our data binary, let’s convert it into a list of bytes and chunk it into our lines of sixteen bytes:

|> :binary.bin_to_list()
|> Enum.chunk_every(16)

We want to divide each of our lines of sixteen bytes into two groups of eight (or fewer) bytes. If we don’t have enough bytes to create our second group, we’ll append an empty list to fill its place:

|> Enum.map(&Enum.chunk_every(&1, 8))
|> Enum.map(fn
  [a] -> [a, []]
  [a, b] -> [a, b]

Now we’re left with a list of lines. Within each line is a list of two eight byte groupings.

We’ll use the index of the outer list to calculate and render how many bytes we’ve dumped so far. We’ll need to attach that to our list with Enum.with_index/2:

|> Enum.with_index()

Finally, we’ll map our lines over a function that transforms each line tuple into a string, and we’ll join the resulting list of strings with newlines:

|> Enum.map(&line_to_string/1)
|> Enum.join("\n")

Our line_to_string/1 function is a helper that accepts a tuple of eight byte parts and the current line index, and returns the string representation of the current line:

def line_to_string({parts, index}) do

The first job of line_to_string/1 is to build the current byte count in hex. The byte count needs to be padded to at least eight characters:

count =
  |> Kernel.*(16)
  |> :binary.encode_unsigned()
  |> Base.encode16(case: :lower)
  |> String.pad_leading(8, "0")

Next, we map over each eight byte part of our line. We render each byte in each part into hex by converting it into a binary using Erlang’s :binary.encode_unsigned/1 and rendering it into base sixteen with Elixir’s Base.encode16/2. Next, can join the characters in each of our parts with spaces and pad the result to twenty three characters using String.pad_trailing/3:

bytes =
  |> Enum.map(fn bytes ->
    |> Enum.map(fn byte ->
      |> :binary.encode_unsigned()
      |> Base.encode16(case: :lower)
    |> Enum.join(" ")
    |> String.pad_trailing(23, " ")

The ASCII component of each line is rendered in a similar way. Because we don’t want a divider in the middle of our ASCII rendering, we’ll flatten our eight byte parts and map each byte over a function that converts it into a printable string. If the byte falls between 0x20 and 0x7E, we convert it into a string. Otherwise, we return ".".

ascii =
  |> List.flatten()
  |> Enum.map(fn byte ->
    case byte <= 0x7E && byte >= 0x20 do
      true -> <<byte>>
      false -> "."
  |> Enum.join("")

Now we can flatten our byte count, each of our two byte parts, and our ASCII representation into a single list and join them together with two characters of whitespace separating each component:

[count, bytes, ascii]
|> List.flatten()
|> Enum.join("  ")

And that’s it!

We can safely use our new Hexdump module to safely and quickly create a hex dump string of any binary packets encountered by our application:

  0xF9, 0xBE, 0xB4, 0xD9, 0x76, 0x65, 0x72, 0x73,
  0x69, 0x6F, 0x6E, 0x00, 0x00, 0x00, 0x00, 0x00,
  0x55, 0x00, 0x00, 0x00, 0x9C, 0x7C, 0x00, 0x00
|> Hexdump.to_string()
|> IO.puts()
0000  F9 BE B4 D9 76 65 72 73  69 6F 6E 00 00 00 00 00  ....version.....
0010  55 00 00 00 9C 7C 00 00                           U....|..

Final Thoughts

What an adventure. The moral of this story is that using the tools and resources available to you is fantastic in the right situations.

That said, it’s important to always be aware of the downsides and potential costs of using existing solutions. Sometimes, rolling your own solution is the right choice. In my case, using the command line version of hexdump would have been horrendously insecure and most likely less performant than implementing my own solution.

If you’re interested in the full source of the Hexdump module we created in this article, check it out on Github.

Shutting Down and Open Sourcing Inject Detect

Written by Pete Corey on Apr 2, 2018.

It’s with a heavy heart that I’m announcing that my security-focused SaaS application, Inject Detect, is shutting down.

The goal of Inject Detect was to fight against NoSQL Injection vulnerabilities in Meteor applications. I still believe that this is a worthy cause, but I don’t think the approach taken by Inject Detect was the right one.

I talked with many customers and their primary concern with Inject Detect was the idea of sending their applications’ queries to a third-party service. No amount of explaining that only the structure of these queries, not the queries themselves were being transmitted could assuage their worries.

It makes me happy to think that my customers’ focus on security dissuaded them from using an application focused on security, and it’s obvious, in hindsight, that this would be an issue.

Inject Detect was the largest Elixir-based project I’d ever worked on at the time it was released, and it was my first real foray into the world Event Sourced systems. I invested nearly six months of my free time and time between client engagements working on Inject Detect, and I don’t want that work to go to waste.

With that in mind, I’ve decided to open source the Inject Detect project on Github. While you’re digging through the code, be sure to check out the InjectDetect.CommandHandler module and the InjectDetect.State module. These two modules are the heart of the system and the driving force behind my implementation of Event Sourcing.

Truth be told, I’m still in love with the concept of Event Sourcing, and I believe that it’s the future of web development. I plan on spending more time in the future diving into that topic.

While I’m shutting down Inject Detect, I’m not giving up the war against NoSQL Injection. Instead, I’m doubling down and focusing my efforts on my newest project, Secure Meteor.

Secure Meteor is an upcoming guide designed to help you secure your Meteor application by teaching you the ins and outs of Meteor security.

If you’re a Meteor application owner, a Meteor developer, or are just interested in Meteor security and NoSQL Injection, I highly recommend you head over to www.securemeteor.com and grab a copy of my Meteor security checklist.

RIP Inject Detect. Long live Secure Meteor!