Author Archives: admin

Selectively Disable-able Java CSRF Filters in Play! 2.5

I’ve written a little bit about CSRF (Cross-Site Request Forgery) protection before. Play provides strong CSRF protection out of the box, which is one of the things I like about the framework. To enable across-the-board CSRF protection, you create the following file, at app/filters/Filters.java:

Then enable the CSRF filter in application.conf:

And add a dependency for filters to build.sbt:

This will apply Play’s default, strong CSRF protection to every request which contains any cookies in the header.

In some cases, though, it’s important to be able to let cross-site requests happen for some (but not all) requests. In this case, ‘forgery’ is a misnomer, because we want the user to be able to make a request from our world-facing app, hit a microservice (for, say, authentication), and see results rather than being unceremoniously kicked out by an error message.

The most straightforward way to do that is with a blacklist: instead of you add an @RequireCSRFCheck annotation to all the form post methods which require CSRF filtering, and an @AddCSRFToken annotation to the action methods which generate those forms. This is tedious if you have many methods which require CSRF filtering and few that don’t. It’s also error-prone, and any oversight results in your security failing open rather than closed, which is not what we want.

Fortunately, although it’s not quite as straightforward, we do still have the ability to selectively disable a global CSRF filter, with just a little work. Moreover, we can do it in Java!

Steve Chaloner provides an excellent answer on StackOverflow detailing how to decorate Play’s routes file with comments to disable CSRF on a per-action basis. At SoFi, we like annotations, so we did it a little bit differently.

First, define an annotation:

We’ll use this annotation on any action method we don’t want to protect against CSRF.

Having defined the annotation, we then define a custom CSRF filter, which will replace the CSRFFilter in Filters.java. Save it as app/filters/AnnotationDisablableCSRFFilter.java:

The important distinction between my solution here and Steve’s solution from the stackoverflow answer is that we’re grabbing the class and method to which the request was made, then inspecting it for the presence of our @DisableCSRFCheck annotation.

Having implemented our custom filter, we then update the constructor of Filters.java, replacing the default CSRFFilter with our AnnotationDisablableCSRFFilter:

Whereupon we can go through and apply the @DisableCSRFCheck annotation to the action methods we wish to open to cross-site requests.

Hello World in Spark with SBT

The code for this post appears in this github repository.

Spark is a promising little Java web framework, suggested to me by my boss after I wrote a microservice in Play!. I believe his exact phrase was “Why?” and that the question was legitimate because Play! is heavier than you need for just spitting out JSON.

I still like SBT over just Maven, because I am lazy and do not want to have to manage my pom.xml. Spark’s tutorials assume you’re using Maven, so here’s what I did instead, just for posterity.

First, build.sbt:

The important difference from what you’d get by doing “activator init” to get a new Play! app is the last line, which tells sbt where to find the project’s main method.

I also wanted /project/plugins.sbt in order to make the “sbt eclipse” command available:

Finally, the Java source for the application:

That’s it!

I just screwed up a coding test!

I’m sitting here beating myself up. I started writing this 3 minutes after sending this email to my recruiter at Amazon:

Please find attached my attempt at this exercise. I do not believe I have successfully fulfilled the requirements, and in fact I’m throwing a null pointer exception, but as I have run out of time, I’m turning it in anyway.

If there’s one part of the interview process I’ve never worried about, it’s the take-home coding test. Generally they ask me to write FizzBuzz or something, and that’s easy enough. Dropbox gave me a cool little array-traversal that took very little time, once I saw the trick. Axiom asked very easy questions, since I was a student, and didn’t bother with the take-home coding test since I was local. When I moved internally to the engineering division of Janus, the phone screen involved swapping the color of an image stored as a byte array. The in-person interviewers broke out FizzBuzz and the bar raiser broke out Dropbox’s problem again (didn’t get it that time, oddly enough).

If I’m sitting in my old accustomed chair in my home office, typing on my machine and using my IDE, there are no problems I could be reasonably asked to solve on this time scale which escape the mighty reach of my intellect. Nobody’s giving out hard-core domain-specific take-home tasks which require special knowledge of undocumented libraries. You’re looking at standard libraries, familiar languages, and choice of tools. It’s nice.

Usually.

In past cases, either the problem’s simplicity made  it very doable or the time scale was generous enough to let me muddle through and wait for the flash of insight. This time, the time scale was an hour, and I spent the first half of it trying to generalize one of my old data structures from the blog while switching the language in which it was written. Don’t do that, guys.

I shouldn’t tell you what the data structure was, since the PDF of the assignment has a big bold ‘CONFIDENTIAL’ footer on it. It’s a generalization of one I’m familiar with, though, both in the structure of the nodes themselves and in the relationships between those nodes. I spent so much time trying to work through the data structure and the algorithm that I ran out of time on the client code to test it, and my submission has a null pointer exception. To say that it’s a little embarrassing would be an understatement.

So, what’s the lesson here?

  1. I need to study more. The comfortable baby data structures I’ve been playing with aren’t going to cut it. I could’ve given ’em a hash table, sure. They didn’t want a hash table.
  2. I need to study more. Data structures are great and all, but I need algorithms – I kinda half-assed a breadth-first search, but I’m not sure my recursion step actually made any sense. The generalization of the structure isn’t to blame, here – I couldn’t figure out how to store the restrictions of the structure’s definition across the steps of the recursion.
  3. I need to study more.

Procedural Map Creation for Crusader Kings II, Part 1: Voronoi Polygons

One of the greatest things about being alive in the 21st century is that other people provide source code on the internet for free. One such person calls himself BenDi, and he saved me the trouble of implementing an algorithm to compute Voronoi diagrams myself. Furthermore, one Maxim Barsuk provided example client code for BenDi’s project, which I was able to modify to suit my needs. 

Specify a set of points, call them ‘seeds,’ and distribute them upon a plane. Given those points, we can make a Voronoi diagram, showing the plane divided into polygons in such a fashion that each polygon contains those points which are closer to a given seed than to any other. Each polygon will be a county for our random CKII map.

A Voronoi diagram. Seeds are the red circles.

A Voronoi diagram. Seeds are the red circles.

I still have some work to do to color the polygons as the CKII engine demands, but this is a good start.

Procedural Map Creation for Crusader Kings II, Part 0: Motivation

One of my long-term goals was to build a completely procedural game, a la Minecraft, but with a deep story. Dwarf Fortress is an effort to do something similar, but it’s very much a depth-first effort, both in terms of gameplay and in terms of world building. The world has much more detail than I could readily use as a player, and the user interface is overwhelmingly complex. Furthermore, while there are great stories told during world generation, the player can’t be part of them: there’s no way to see the consequences of your actions on a global scale. Time stops when you start your fortress. Nations don’t fight wars while you’re on adventures. The player can successfully clear the world of certain types of beasts (the game will often recognize this; if there are only a few great monsters left in the world and you kill them, a ‘new age’ will dawn) or totally destroy a nation of goblins, but nobody will move to fill the power vacuum they leave behind. I’m not faulting Toady for this: he’s given us a very deep and immersive world, down to realistic geology and tracking every elf’s every tooth, but his universe isn’t precisely what I want.

Enter Crusader Kings II. CK2 is a ‘grand strategy’ game, in which the player takes control of a medieval dynasty, starting some time after 867 and ending in 1453, when the game’s approximation of feudalism no longer accurately represents political reality. Cities aren’t simulated down to streets, and the only people who have any agency are noblemen, clergy and mayors. Tactics have no place in war: the player can order his armies about in a mass, but only with enough fidelity to send a ten thousand men to York. He does not order them about on the field or even decide which part of York to control. The day-to-day details of the realm are abstracted away, in other words, almost completely. Instead, the player manages the human relationships between noblemen, arranging marriages to forge alliances, granting lands to barons to curry their favor, or changing inheritance laws in order that a genius third-born son might ascend the throne instead of his inbred eldest brother.

It sounds dry, and it is dry, but it’s the only game out there which really allows the player to play the game of thrones we see in A Song of Ice and Fire or Dune. With more depth in any particular area, it would become a tactical simulator like the Total War series or an accounting simulator or a dating simulator. As it is, it creates very interesting, dynamic alternate histories on a grand scale, and allows the player to feel a monarchical pride in having (for instance) repulsed William the Bastard at Stamford Bridge, or brought the Caliphate all the way north to Scandinavia.

As it allows the player to play the game of thrones, it was the perfect platform on which to build a Game of Thrones mod. The diplomacy in the game is deep enough to allow for the plots and alliances the books and TV show are built around, and the feudalism accurately represents the relationships between lords and their bannermen.

The GoT mod is a total conversion mod. That means it has a completely custom map, entirely new art assets, different cultures, and different events. Other total conversion mods exist; the next most famous being set in the world of The Elder Scrolls.

I see no reason why it shouldn’t be possible to create such mods dynamically, to procedurally generate the world’s map, the noblemen in charge of each area, and the relationships between them. Generating those dynamic worlds would allow dynamic, sensible stories to play out in a fantasy world, and I think the idea very appealing.

A Queue in C#

A queue (pronounced as one would the letter ‘Q,’ although the grad student who taught my Data Structures course was fond of saying ‘kway-way’ to remind us of the spelling) is analogous to a stack, but our access to the data is at the element first added, not the element most recently added. It’s just like the line at McDonald’s or at the bank or a queue in Britain, where imitating data structures is a national pastime. Instead of being named ‘push’ and ‘pop,’ the operations are called ‘enqueue’ and ‘dequeue.’

queue

 

Queues are a very ‘fair’ means of determining priorities. As already mentioned, we use them to determine who is served next at a restaurant. A printer uses a queue to determine which job to handle next, in case multiple jobs are submitted while another is being handled.

Like a stack, a queue is implemented atop the scaffold of another data structure, like a list or an array. Since I did the linked list in C#, and we’re back around to C# in this example, I’ve built my toy queue on my own toy linked list, rather than using .Net’s built-in linked list:

As you can see, my earlier laziness in not fleshing out the linked list’s optional functionality made matters a bit more complicated. If the linked list tracked its last element and offered the ability to delete from either end, the dequeue method could be a bit simpler. As it stands, we have to walk through the entire queue every time we want to dequeue anything. It’s as if our maître d’ or bank teller starts at the end of the line, asking each customer “Was anyone here before you?” and determining whom to serve that way.

We also add another little test to our DataStructureTesters project:

Which gives the expected output:

A Stack in Python

A stack is an ordered collection which offers two operations: ‘push,’ adding an item to the stack, and ‘pop,’ to remove and return an item. ‘Pop’ will return the most-recently-pushed item which has not been previously popped. The physical analog is a stack of plates like the one you might find in your kitchen cabinets: supposing you are only strong enough to handle one plate at a time, you’ll always add (‘push’) a plate onto the top of the stack, or remove (‘pop’) the last plate you pushed.

stack

Those are the only two operations you get. It can be counterintuitive, but limiting what you’re able to do with the collection like this is pretty useful. Your web browser two stacks for your ‘back’ and ‘forward’ buttons, popping a page or URL from the from the ‘back’ stack and pushing the current page onto the ‘forward’ stack when you hit the ‘back’ button (or vice-versa). Your computer’s memory contains a ‘call stack’ for every application, which keeps track of the subroutine that application is currently executing. This allows us to call subroutines from other subroutines and return to the point where we left off.

Internally, stacks are usually built on top of lists, either array lists or linked lists. In fact, my linked list from the original post is already a stack, but with the ‘push’ and ‘pop’ operations named ‘insert’ and ‘delete.’ The difference is that a full-featured linked list would probably have some functionality to insert and delete at the tail or perhaps at an arbitrary position in the list, whereas a stack shouldn’t (if it does, it’s not a stack any more).

Since we’ve already implemented a linked list, I’ll take Python’s built-in list structure for granted, and just implement the stack on top of it:

This gives the expected output:

Now, even the casual observer will note that I made this a little more difficult than it could’ve been. Python’s lists already define a “pop,” but using that would’ve been silly.

In a real setting, we’d probably want to implement a ‘peek’ method, which would allow us to get the item atop the stack without popping it. With this toy example, we’d have to pop the item, use it, and push it back onto the stack. We might also want an isEmpty method, or a more graceful behavior when we try to pop from an empty stack (right now, we get a “list index out of range” error).

FizzBuzz!

Jeff Atwood of Coding Horror wrote a post back in 2007 lamenting the incompetence of applicants to programming jobs. He used “FizzBuzz” as an example of a problem that every programmer ought to be able to solve. The statement is simple:

Write a program that prints the numbers from 1 to 100. But for multiples of three print “Fizz” instead of the number and for the multiples of five print “Buzz”. For numbers which are multiples of both three and five print “FizzBuzz”.

Readers took this as a challenge, and posted their solutions in the comment section. Some of these solutions did not satisfy the requirements. I think most of those programmers could come up with workable solutions if they understood the spec.

Atwood’s follow-up post instructed the readers not to bother with FizzBuzz, since that wasn’t the point of the discussion, but I think publicly presenting solutions to simple problems like this will help me get a job when I finally need one.

As such, I present my FizzBuzz solution in PHP. This isn’t optimized at all, in part because the goal of the exercise is to show the interviewer (or reader) how I think.

In plan English:

  1. Repeat the following steps for the integers from 1 to 100, inclusive.
  2. If the integer is a multiple of 3, write “Fizz,” and make a note of the fact that you wrote something.
  3. If the integer is a multiple of 5, write “Buzz,” and make a note of the fact that you wrote something.
  4. If you didn’t already write something for this integer, write the integer itself.
  5. Write the next thing on a new line.

Some other correct solutions treat multiples of 15 as a special case, which allows them to use ‘else if’ and refrain from making a note of whether we’re supposed to write the integer. That’s probably no less robust, but my immediate instinct upon reading the problem statement is what I wrote above.