More on ONCOgen: What Is Context-Free Grammar?

This post contains more details about the inner workings of ONCOgen, a software program that can generate New England Journal of Medicine-formatted clinical trials. You can read more on the ONCOgen page or at the first post in this series.

When you pick up a scientific paper the expectation is that a certain, specific set of information is included in the manuscript that allows the reader to understand why the experiment was performed, what experiment was performed, what the results of the experiment were, and how they were analyzed. While we expect the authors to provide their interpretation of the results and their significance, we as the readers rightfully expect to have enough information to judge the results for ourselves.

In broad strokes, the information in every clinical trial comes through in four major sections:

  • Background & Introduction
  • Methods
  • Results
  • Discussion

Each of these can be subdivided further. For example, a Methods section may include any or all of the items below:

  • Patient Population
  • Study Design
  • End points
  • Assessments
  • Statistical Analysis
  • Study Oversight

While each section might be worded a little differently or subsections might be more or less inclusive,  everything should be there. You can keep breaking this down further: a sentence or two about inclusion criteria; a sentence about the a priori significance level; and a few sentences describing the target disease with lab values or specific biomarker requirements.

For the purposes of writing a fake paper, the high-level structure of a paper seems like an easy target; even the paragraph level seems pretty straight-forward. But there are practically a million ways to say, well, stuff. How do you make semi-convincing fake verbiage?

Well, we have to zoom in a little more for that.

Continue reading More on ONCOgen: What Is Context-Free Grammar?

ONCOgen: the Clinical Trial Generator

Atezolizumab is an inverse JAK2 enhancer that has been shown to increase PD-1 capilloactivity in cytocytes and adipocytes. There has been collaborative research in the classification of transdisciplinary dactylical cardiolyses which gives reason to believe that geriatric biophysics could have applications in newly diagnosed, platinum-resistant, CD93-positive myeloproliferative disorders. In our research we validated the menigotolerability of entero-BCR-ABL enhancers on keratoparesis risk in volunteers with renal cell tumors.

Update: a more detailed look at the inner-workings of ONCOgen are detailed here.

ONCOgen is a software program that uses context-free grammar with an extensive library of medical terms and phrases derived from over a thousand clinical trials, drug information resources, and personal experience to “randomly” generate a clinical trial manuscript. Context-free grammar is, at its core level, a set of rules for computer generated mad-libs.

Not just a fun play on words, ONCOgen is designed to be the spiritual successor to other applications of context-free grammar such as SCIgen—which generates computer science papers—and Mathgen—that generates high-level math papers. SCIgen became notorious after having one of it’s papers accepted to a high-profile conference and later, the announcement that over 100 SCIgen-generated papers and abstracts were being retracted from prominent subscription publishing houses. Another major story surrounded the submission of a faked paper to 304 open-access journals. In the end, 157 (52%) of journals accepted the hopelessly flawed experiment.

Consider arXive vs snarXive (archive versus snark-ive), a game where the user is asked to guess which of two high-energy physics paper titles are real—one pulled from a database of such papers and the other computer generated. The overall correct guess rate sits around 59%. I went 1 for 6 on my first attempt. Why is this so hard? Jargon, abbreviation, and good-old-fashioned benefit-of-the-doubt.

Just like the jargon in high-energy physics or doctorate-level mathematics, medicine has its own set of buzzwords and thankfully, an enormous set of prefixes, suffixes, Latin and Greek root words, and arcane sounding but systematic naming conventions. Add to this the standardized journal-ready formats for clinical trial manuscripts whose structure makes these documents amenable to this kind of reductionist approach.

Unfortunately, in order to generate properly formatted papers ONCOgen needs LaTeX and a few additional things on the backend that my current website hosting provider is unable to accommodate. Until then, I have provided a number of pre-generated abstracts here that you can “generate” on the ONCOgen page.

Take me to the papers! or, a more detailed look at the inner-workings of the program.

Principles of Password Design

Try to guess the most secure password:

  1. a3@Bs!14z21Hb&!@mO89
  2. LazyBumblebeesEvenOrange

Passwords are the face of computer security. Just about everything you use online or off—more often than not—requires an account and an associated password. Ultimately, the goal of that requirement is to simply provide a form of identity verification, asking: “is the person sitting behind the keyboard right now the same person that should have access to this resource?”

Unfortunately, passwords are one of the weakest forms of identity verification, especially as used by the vast majority of the computer-using population. To combat this, websites—particularly those where money is involved—began using password requirements to enforce security when creating a login. While this used to be entirely the purview of banking sites, the proliferation of largely arbitrary, complex, and nonstandard password rules often DECREASE the relative security of the password that the user invents. On top of this, the sites implementing these complex rules often undermine their entire schema by incorrectly managing their database or enforcing additional arbitrary requirements.

For some context here, check out some of the most common passwords:

I hope to illustrate some of the weaknesses of passwords by walking through some of the basic password attack vectors and the elements of cryptography employed in their creation. Hopefully, you can use this information to create more easily remembered, secure passwords.

Password Search Space/Depth

Have you ever considered why websites ask you to include UPPERCASE, lowercase, a number, and a symbol in your most secure passwords?

This is the first principle of password design: the number of permutations, or the “search space” required to brute force your chosen password. You might remember from highschool the principles of combination versus permutation. As you can use the same letter, number, or symbol multiple times and the order of the characters matter, passwords use permutation, not combination. So how can we apply this?

Take your typical four digit PIN: 1111. Let’s list our assumptions:

  • Each character is a number from 0-9.
  • There are four characters.
  • Numbers can be used more than once and can be in any order.

Based on what we know, we can conclude that there are 10^4 (10,000) permutations, where 10 is the number of possible characters (0,1,2,3,4,5,6,7,8,9) and the exponent is the length of the password. Starting at 0000, then 1000, then 2000 all the way to 9999 we can simply generate each permutation of digits, try the PIN, and if it fails, try the next one. This is the essence of brute force password cracking—there is no information to guide the search—we just try each and every permutation until one of them works.

So what happens to our search space when we change the rules? Let’s look again at our four character PIN if our user can also use lowercase letters. There are 26 lowercase letters: with our 10 digits + 26 lowercase letters the number of possible characters is now 36. Our password is still four characters long, so our exponent is still 4, giving us 36^4 or possible permutations. Adding UPPERCASE (another 26 characters), and symbols (another 33 characters) additionally increase our search space.

  • Numbers: 10^4, 10,000
  • Numbers+lower: 36^4, 1,679,616, 167 fold increase over numbers
  • Numbers+UPPER+lower: 62^4, 14,776,336, 8 fold increase over numbers+lowers
  • Everything: 95^4, 81,450,625, 5 fold increase over numbers+UPPER+lowers

If I were to brute force—generating each possible combination at a conservative 1,000 guesses per second (a speed easily achievable by many graphing calculators) it would take just 10 seconds to crack our numbers-only password, about 30 minutes for our numbers+lowercase, all the way up to about 22 hours for our full keyboard.

It becomes evident why websites like to require increased complexity, forcing you to use UPPER and lowercase, symbols, and numbers when creating your password. Unfortunately, this has the side-effect of forcing the creation of passwords like @Aj8, V&t1Kv4s, or Ba#$J5—passwords that are not only difficult to remember but are missing another crucial piece of the password puzzle.

Knowing what you know now, which of the following passwords will take the longest to guess?

  1. 3ED45
  2. 3eD45
  3. 3ed4%
  4. 33445

Given that all of these passwords are five characters long, C has numbers, symbols, and lowercase letters, the largest search space.

KEY: A: 17 hours, B: 1.5 weeks, C: 2.6 weeks, D: 2 minutes

Password Length

For the first element, we focused on the base number of the permutation calculation, starting with 10 and ending on 95. As you might imagine changing the exponent you can change the number of permutations by orders of magnitude. In the previous example, our password was four characters long, what happens to our permutations if we add just one character?

Numbers only: 10^5, 100,000, 10 fold increase over 4 characters

Numbers+lower: 36^5, 60,466,176, 36 fold increase over 4 characters

Numbers+lower+UPPER: 62^5, 916,132,832, 62 fold increase over 4 characters

Everything: 95^5, 7,737,809,375, 95 fold increase over 4 characters

Notice a difference? Unlike the diminishing returns we observe when incrementally increasing the search space at a given length, we see literal exponential increases in the search space by simply adding one or two characters.

Revisiting our graphing calculator brute force attempt (1,000 guesses per second), cracking our everything-password goes from 22 hours with four characters to nearly six months with five, an enormous difference.

We aren’t finished yet: we’ll now look at the final and most important component.

Using similar passwords from the previous section, which of the following passwords will take the longest to guess?

  1. 3ED4517
  2. 3eD45
  3. 3eD4%
  4. 3344526

Despite C encompassing the largest search space (an everything password), both A and D are two digits longer. However, despite what you might hear on TV, length is not everything. D (appropriately) only contains numbers—a very small search space—which despite the increase in length leads to a relatively small number of permutations and by far the shortest brute force time. Choice A with a mix of length and search space leads to the longest brute force time of these options by a considerable margin.

KEY: A: 2.5 years, B: 1.5 weeks, C: 3 months, D: 3 hours

Password Entropy

This one is a little more complicated than the previous two. Just like we learned in thermodynamics, entropy is randomness. Therefore, a strong password will have a high degree of randomness that makes it difficult to guess. Essentially, password entropy is a mathematical measure of a passwords “guessability” by a brute force attack. Recall the brute force method: generate each password permutation in order, aaaa > baaa > caaa etc. Assuming that we, as the attackers, know the password generation rules, we can determine the size of the search space and the probability of guessing any password at random. It stands to reason then that a randomly generated password with n characters will sometimes be generated very early in the total search space (if the password was aaaa, for instance) and sometimes be generated very late (in the case of zzzz). On average, a brute force attack will find the password half-way through a given search space. Mathematically, we can represent the number of “bits” of entropy via the base-2 logarithm of the total number of permutations.

To illustrate this, let’s return to our first four digit PIN: 1111. Our total search space was 10^4, or 10,000 permutations. By taking the base-2 logarithm we can determine the number of bits of entropy. 10,000 = 2^n, or 13.288 bits of entropy.

Now what would a password look like with just one additional bit of entropy?

2^14.288 = x, giving us a total number of permutations of 20,000. As you might expect given a base-2 logarithm, one additional bit of entropy doubles the number of guesses required for an attacker to find the correct password.

In a way, entropy is an extension of our first and second principles. Both length and search space factor into the entropy of a password. If entropy is entirely based on the number of permutations and that is based entirely on our first and second principles, why exactly are we talking about this?

The reason is randomness. Humans are ludicrously bad at coming up with random passwords and computers are only slightly better. Unlike the prior two principles, entropy is important due to the social engineering component of brute force attacks, something I will cover further in the future as it is beyond the scope of this discussion.

For now, we’ll focus on what “randomness” actually means in this context. Surely, the password GmKa$5VM is random but in what way? Each character was chosen as randomly as possible from a character space of 95 possible choices, giving about 6.5 bits of entropy per character (see here for how per character entropy is calculated). The idea here is that we can randomly generate passwords with a high degree of entropy; however, these passwords are a nightmare from a usability perspective. Most people have trouble remembering more than a small handful of password, let alone ones that are literally designed to be pattern-free.

But what if we come at this from another direction? Take Diceware for instance, a wordlist that contains 7776 short, English words. If we were to randomly select a word from this list, the possibility of correctly guessing any random word is 1/7776 or nearly 13 bits of entropy per element. Compare this to the probability of guessing any random character: 1/95. As bit strength entropy is additive, we get an entropy of a randomly selected password “aaaa” (6+6+6+6) of 24 bits. Selecting four random words from the Diceware list: “climbharrowjumpalong” gives us a total entropy of (13+13+13+13) 46 bits of entropy entirely independent of length.

Ultimately, entropy is about creating passwords that are unique and difficult to guess.

The Takeaway

We’ve covered three principles of creating a strong password:

  • Search space: the number of possible things that each character in a password is drawn from,
  • Length: how many characters you need to guess correctly and in the proper order
  • Entropy: how unique and difficult to guess your password is, as a measure of the other principles

It is important to remember that none of these principles alone can create a strong password. The word “password” is eight characters long (not a minimal acceptable length, in my opinion) but is also one of the most commonly used passwords on the planet. The a@B4 covers the search space requirement but is only four characters long. However, the password that combines both of the first two elements, “a@B47N%p” is virtually impossible to remember! As Randal Munroe of XKCD points out, we have been training users for decades to create passwords that are both difficult for humans to remember and easy for computers to guess. My online banking site, for instance, requires numbers, letters (both upper and lower case) and symbols, but caps passwords at EIGHT CHARACTERS, almost entirely defeating the purpose of the increased search space.

So how can we create passwords that are both usable and secure?

Passphrases: picking several words at random from a dictionary or creating a unique sentence. Bonus points for incorporating punctuation and numbers for search space considerations.

Site-handing/padding: adding between 5-10 memorable characters to the beginning or end of your password. Ideally, these characters can be generated from some aspect of the site you can easily remember.

The world of IT security is enormous and these techniques only scratch the surface of things that you should be considering when keeping yourself safe online. I hope to cover more of the social engineering aspects in a future DYK, but for now, think about your passwords? How long would this take to crack on my graphing calculator, let alone my GPU used for video gaming, or the supercomputer used by a motivated nation-state? You can put it to the test and find out.

For some further reading, check out this paper from Microsoft about common user password creation habits. You’ll probably be surprised (or not) to find out how users create passwords.

Now, after all of that, which of the passwords above is the most secure? At this point, you’re probably unsurprised to learn that password 2—LazyBumblebeesEvenOrange—is orders of magnitude more secure than password 1. Just don’t go using it anywhere!

Happy security!

All About Speedrunning

Remember all of those games you played as a kid? Games like Mario 64, Ocarina of Time, Banjo Kazooie, and the like? Well you might be surprised to learn that there exists an entire subculture of people who try to complete these games as quickly as possible. From what I understand speedrunners live for the sake of the puzzle; figuring out all the programming quirks, tricks, and unexpected oddities that make each game unique. In programming, this is known as an “optimization problem,” or the process of finding the ideal solution to a set of parameters.

To give you some perspective, the world record speedrun for Zelda: Ocarina of Time is just a few seconds over 18 minutes. I know what you are probably thinking right now. Allow me to explain how something like this is possible.

In competitive speedrunning (and yes, there are competitions) there are a number of types:

No-glitch, where players go through the game as any normal player would, finding the optimal path through movement and mechanics, completing the game as the developers intended.

Glitch, where players take advantage of (usually fascinating) programming errors or memory mis-allocation to do something they could otherwise not do, such as clip through a wall to get to a new area or get an item they otherwise would not get for some time. They do not play the game as the developers intended, but work entirely within the game itself.

Tool-assisted: the optimization problem in the literal sense, writing a computer program to aid the player in completing the game in the most optimal way (down to the frame) or write to the game’s memory to allow certain behaviors. These players use external tools to allow them to complete the game more quickly.

Beyond this, there are several other sub-classifications that I won’t go into now that deal with %completion and other game specific objectives. There is a lot of granularity.

That Ocarina of Time speedrun is the world record glitch playthrough, working entirely within the game but clipping through walls, using movement and damage bugs, and moving through and around areas in ways the developers did not intend. Executing many of these glitches requires an enormous amount of skill and timing that I personally do not possess.

Remember those competitions I mentioned? Beyond just informal ones, there was an enormous annual fundraiser that had many of the worlds best speedrunners stream live for a week straight (24hr/day) that raised $1.5 million for charity. Yes I watched it. Yes it was pretty cool. Not to mention that people will actually compete to see who can complete the game the fastest, all starting at the same time (a race).

If you are interested in watching an 18min Ocarina of Time speedrun, the previous world record holder (3s slower than current, that is how quickly that this world moves) did a commentary about how some of these glitches were discovered, what he does to execute them, and that also serves as a good background to the community in general and the history of the game itself.

When things get crazy is when you enter the world of tool assisted speedruns (TAS), allowing you to do absurd things (such as writing a game within a Pokemon Red cartridge by changing the number of Potions or Pokeballs that you have, altering the memory value at those locations, then running it as a program) or program the entirety of Super Mario Brothers within Mario 64 by taking advantage of a buffer overflow. Stuff like this seriously blows my mind. Check out this article on ArsTechnica that explains a lot of what they did.

So there you go, a little bit about speedrunning. Chances are, if you played it, people speedrun it, Take a peek at how quickly they’ve beaten your favorite game. Note that all of these are “any%” meaning that they get through to the end titles as quickly as possible, skipping anything that is unnecessary (as opposed to 100% runs).

The Physics of the Impossible Drive

Around this time last year a series of small experiments run at Eagleworks—a NASA research and development lab—became big news. The subject of these experiments—the EmDrive and the Cannae Drive—are two independently invented “reactionless” propulsion systems.

Why are these experiments so exciting? The way that these drives may be working turns our understanding of physics on its head. As you might be familiar ,all chemical rockets (think the Apollo or fireworks) work on more-or-less the same principle: direct the rapidly expanding gasses from the combustion of fuel and an oxidizer through a nozzle. The focused hypersonic movement of the gas pushes the rocket in the opposite direction through the conservation of momentum (Newton’s Third Law). Other types of rockets, such as ion rockets (, utilize the same principle by accelerating gasses to high speed using an electromagnetic field. Rockets that work in this manner are collectively known as reaction rockets.

Reaction rockets all share one critical drawback: they all must carry their own fuel. Fuel is heavy, I’ll let Randal Munroe of XKCD explain why this is a problem:

“If we want to launch a 65-kilogram spaceship, we need to burn around 90 kilograms of fuel. We load that fuel on board—and now our spaceship weighs 155 kilograms. A 155-kilogram spaceship requires 215 kilograms of fuel, so we load another 125 kilograms on board…

…fortunately, we’re saved from an infinite loop—where we add 1.3 kilograms for every 1 kilogram we add—by the fact that we don’t have to carry that fuel all the way up. We burn it as we go, so we get lighter and lighter, which means we need less and less fuel. But we do have to lift the fuel partway.”

For decades, long-term space exploration has been limited by the fuel problem and continues to represent a significant practical barrier. Overcoming the fuel problem would be a breakthrough of untold magnitude.

After all of that, what exactly is this reactionless drive? Chances are if you have read/watched/played any science fiction, a staple of faster-than-light space travel was a reactionless drive of some sort—an engine able to generate thrust without focusing the exhaust from the combustion of a propellant. Unfortunately, basic tenets of physics are not on our side. Remember Newton’s Third Law and the conservation of momentum? The same reason that a figure skater spins faster when they tuck in their legs is the same reason that rockets work at all. Removing the high-speed exhaust (and its mass) from the equation there is suddenly no force to move your rocket. Based on our current understanding of physics such an engine would indeed be an “impossible drive.”

With that, let’s look at the technologies causing the stir and what exactly they seem to be capable of. Before we begin I would like to remind you that we have very little certainty on any of the following; scientists are attempting to document and explain this unusual phenomenon.

Both the EmDrive and the Cannae Drive likely function on similar principles. You might have seen toys like this one that work on the principle that while photons have no relativistic mass, they do still possess momentum (start here for a discussion of this, or for a more formal treatment here). When the photons hit the wheel they transfer a small amount of energy, and with enough of them they overcome friction forces and turn the wheel. This action is known as radiation pressure, a principle loosely analogous to the water pressure that moves a turbine in a hydroelectric dam. The running hypothesis is that rapidly creating photons at specific frequencies in a specially designed chamber allows the particles to be focused out in one direction. Other hypotheses involve phrases like “quantum foam” and “space bubbles” that have not yet been entirely worked out into something cohesive. The inventor of the Cannae Drive claims that the particular shape of the internal cavity is critical to the design, although this has yet to be validated.

Both drive designs were independently tested by Eagleworks at the Johnson Space Center.

EmDrive test summary:

  1. A test at 2500W of power during which a thrust of 750 millinewtons was measured by a Chinese team at the Chinese Northwestern Polytechnical University
  2. A test at 50W of power during which a thrust of 50 micronewtons was measured by Eagleworks at the Johnson Space Center at ~760 Torr of pressure. (Summer 2014)
  3. A test at 50 W of power during which a thrust of 50 micronewtons was measured by Eagleworks at the Johnson Space Center at ~5.0×10−6torr or pressure. (Early 2015)

Now the Cannae test summary. They did three trials with different experimental setups:

  1. The device as the inventor designed it
  2. The device as the inventor designed it without the slotting that the inventor claimed was critical
  3. A control test that used the same energy, but without the cavity present in the design

Results summary:

  1. Approximately 25 micronewtons of thrust at 50W
  2. The same results as test #1, showing that at the very least, the slotting provided no benefit or detriment to the effect happening
  3. No measurable thrust

Tests were conducted on an apparatus that could measure down to 10 micronewtons and in multiple directions. It is important to note that these tests were not conducted in a vacuum like the EmDrive tests.

As you can see, incredibly tiny amounts of thrust are being generated at these low power levels. A force of 50 micronewtons is approximately the amount of force required to launch a few ants into space. Tiny, but significant.

Normally, technology this early in its development cycle—especially one that is throwing a wrench into several well established principles of Newtonian physics—would be greeted by an enormous amount of skepticism. Thankfully this holds true: I have rarely seen more critical discussion about an emerging technology than I have about these reactionless drives. What is certain is that there is something going on here. Whether or not it does turn out to be a reactionless drive remains to be seen. Larger scale tests at a higher power will be completed this year and should provide more insight. A fourth experiment with the EmDrive (not listed above) was conducted with a device called a Michelson interferometer inside the chamber—a device that is capable of measuring changes in spacetime (a gross oversimplification). The device noted changes in the compression of spacetime within the chamber while the EmDrive was activated. If your reaction to that last sentence was anything like mine, this discussion might be interesting.

Should this technology pan out, the implications are enormous. Virtually every form of transportation (including cars, bikes, and planes) in addition to rocketry and space exploration can benefit greatly from the development of a power efficient reactionless drive. I have been following these experiments closely for the last year, and given that they have been turned over for dozens of reviews and still hold any amount of water a year later is exciting.

With developments like these we are one step closer to the world I dreamed of as a child. Outer space gets closer every day.

Further reading:

  1. Papers from the experiments, including a set done by a Chinese laboratory (disclosure: sponsored by the inventor): One Two Three
  2. More detailed write-ups on the EmDrive
  3. Lengthy forum discussion on the experiments
  4. Historical “attempts” at the development of a reactionless drive; which (unsurprisingly) all sounds very similar to the history of perpetual motion machines.
  5. Discussion of the Michelson interferometer experiment
  6. Eagleworks data

The Falcon 9 Lander by SpaceX

SpaceX, a rocket propulsion company founded by Elon Musk (Tesla Motors, Paypal), has been developing a reusable launch vehicle for the delivery of materials to orbit efficiently and for low cost. Currently, the cost of putting one pound of stuff in orbit is about $15,000, largely as the rockets used to deliver these payloads (the Delta and Atlas series rockets) are not reusable and are destroyed completely after launch.

What SpaceX has been working on is a launch vehicle that gets the stuff up there then lands itself automatically on a barge out in the middle of the ocean. Imagine balancing a broom handle on your palm. Now imagine that traveling at thousands of miles an hour. Now imagine your other hand is moving up and down on 30 foot waves and how you have to toss the supersonic broom handle–which weighs over 100,000lbs and is over 150 feet tall–to your other hand and catch it straight up and ever so gently.

You can imagine that this is not an easy task. Here is a Vine of the first landing attempt.

No cigar indeed. Post-mortem: ran out of fuel and hydraulic fluid for manipulating the grid fins that stabilize the rocket. So they tried again today. This was the result.

Much better. Unfortunately it had slightly too much horizontal velocity and tipped over. Still an enormous improvement, and this rocket delivered supplies to the ISS as a bonus.

Already the Falcon 9 has decreased per pound low Earth orbit launch costs by a factor of 3 without the landing capability. I cannot wait until economical launch vehicles finally put the serious development of space within reach.

So excited.

More on the Falcon 9
More on the first test of the lander (includes a post-mortem)