Musings of a Software Engineering Student

On building fast kd-Trees for Ray Tracing, and on doing that in O(N log N)
Ingo Wald, Valstimil Havran

Kd-trees seem to be the most widely used technique for spatial subdivisioning. They are believed to be the best known method for fast ray tracing. The Surface Area Heuristic is the construction technique usually used, and how to building efficient ones and traversing them quickly is well understood. However, constructing them is not as well understood, which is what this paper hopes to analyze.

All kd-tree construction schemes follow the same recursive scene:

function RecBuild( triangles T, voxel V ) returns node
    if Terminate(T,V) then:
        return new leaf node( T )
    p = FindPlane( T, V )
    (V_L, V_R ) = Split V with p
    T_L = all members of T on one side of  V_L
    T_R = all members of T on the other side of V_L
    return new node( p, RecBuild(T_L, V_L), RecBuild(T_R, V_R) )

The difference between a good and a naively build kd-tree is often a factor of two or more. The naive method often used, the “spatial median” method, is to just alternate axis and the plane being split at the spatial median of the voxel.

The Surface Area Heuristic(SAH) tends to perform quite well. It makes several assumptions:

• Rays are uniformly distributed, infinite lines.
• The cost for both a traversal and a triangle intersection are known.
• The cost of intersecting N triangles is roughly NK.

The expected cost for a given plane p then is one traversal step, plus the cost of intersecting the two children. Usually, instead of minimizing the cost of traversing the entire tree, a greedy version of the heuristic is used which minimizes it at each level, due to efficiency reasons. We also need to define a termination criterion; when to stop the recursive build: SAH gives us an elegant one, which is if the cost of this node as a leaf is better than even the best split.

The SAH tends to work best, and only a few modifications are known to consistently yield better improvements. One of these is to favor splits that cut off empty space. Requiring the tree to be split a certain number of times can prevent the tree from being stuck in a local minnima, but this number is hard to determine for general scenes.

There are several ways to construct Kd-trees once you have decided upon the cost function. The mmost trivial way is to iterate all triangles, determine their possible split candidates, and compare the cost for each one. This will end up taking O(N^2) operations, where N is the number of triangles in the scene. This is often too slow.

There is also a widely-known algorithm for constructing SAH trees in O(N log^2 N). I’m not going to summarize the algorithm here: if you are interested, read the paper. It essentially ’sweeps’ a plane, calculating costs incrementally. This is a huge improvement, but as the theoretical lower bound is O(N log N) we wish to be better.

This paper introduces a O(N log N) method of building a kd-tree. What caused the previous algorith to be O(N log^2 N ) instead of O(N log N ) is having to sort once per partition. This algorithm improves on that by sorting the evet list only once. This involves having to events for all dimensions. Again, I’m not going to recap specifics of the algorithm here.

The two algorithms were then compared in actual time, and not just asymptotic behavior. Realistic models of varying size were used. The O(N log N) variant is concisely faster than the O(N log^2 N) variant by a factor of 2-3.5. Analysis shows that the O(N log^2 N) variant spends more time re-sorting than the other variant uses to build the entire tree.

Supporting Dynamic Languages on the Java Virtual Machine
Author: Olin Shivers

This paper is about enhancements to the JVM that would make it easier to port dynamic languages, such as Scheme, to the JVM. This is desirable due to the fact that there is now a JVM for practically everything; running on the JVM means that the language will run on every architecture it will run on. However, the JVM, while well-designed for speed of Java programs, does not support dynamic languages very well. One example of a language that suffers performance problems from this porting process is Scheme. In Scheme, there must be a uniform representation of data - all types can be in cons cells. Working this into the Java class models means that every type must extend Object, and boxing and unboxing is expensive for primitive types.

The proposal to support immediates is to give pointers to Java objects a low bit of one. Since these are allocated on word boundaries, this does not hurt. This allows a final ImmediateDescriptor class that has 31 bits of state that can quickly be converted to an even integer(or vice versa). This causes no penalty to programs not using them - if a method iis called on them, this would generate a memory alignment exception that the VM can catch, which would still be fast.

There are still problems with issues such as method lookup, for example. The JVM bytecode is well-optimized for Java code, but not necessarily other paradigms. There is a tension in the bytecode between verification and efficiency - we don’t want an unsafe RISC bytecode system, we do want a safe system, but this will make it less efficient in few cases. This tradeoff is made well for Java, but not other languages.

A proposal to fix this is to have some of the bytecode instructions to be linked to C routines at runtime. This allows language implementers to efficiently represent whatever they need. However, this brings up the problem of verification - these C routines may be unsafe. The solution to this is to have some central body, where the JVM will ‘checkout’ the required instructions as told by the language implementer, and warn the user if the requested code is not in this standard and must be checked out from an unverified location.

This is a summary of a paper, titled Your Botnet is My Botnet: Analysis of a Botnet Takeover.

Botnets are becoming a large problem for the internet. They are formed by networks of compromised computers that are under the control of some other person. Botnets are becoming the primary means for criminals to launch DOS attacks, steal personal data, or other cyber crimes.

Most previous analysis of botnets have been analyzing them from the inside; intentionally infecting a computer to join the botnet, and analyzing the activity that then occurs. Since many botnets use P2P protocols, other infected computers can be discovered using this technique. However, this gives a very limited view of the activities of the botnet. A better way is to take control of the entire botnet, which can be done either with cooperation from domain registrars or law enforcement.

For this paper, researchers took control of the Torpig botnet. Torpig is primarily associated with bank account and credit card theft. This was done by exploiting how the bots try to locate their command server. Each bot generates a list of domains to contact, and the first host that sends a reply identifying itself is considered genuine until the next domain generating phase. This allowed researchers to register domains the infested host would contact.

Torpig is distributed to it’s victims using Mebroot, a rootkit that replaces a system’s Master Boot Record. Victims are infected through vulnerable web sites being modified so that the victim’s browser requests Javascript, which then attempts several exploits. If any are successful, an installer for Mebroot is downloaded and executed. Mebroot does not perform other malicious attacks itself; It acts as a platform to install malicious modules. Mebroot contacts the C&C server every two hours to receive updates.

The C&C server distributed three modules, which comprise Torpig. These inject these DLLs into the file manager, Internet Explorer, Firefox, and other popular utilities, allowing it to inspect all data handled by these programs. Every twenty minutes, Torpig uploads new data to the command server. In reply to this, the C&C server can either respond with ‘ok’ or a configuration file used for configuration and parameters to perform phishing attacks. These attacks can gain data that would not otherwise be possible by passive monitoring. When the user goes to a site in the configuration file, they will instead be redirected to a site given by an injection server.

Taking over the botnet was fairly simple; domains were registered for a three-week period. Logs were collected from all network data, until a new torpig binary that changed the domain generation algorithm was installed through Mebroot. 70GB of data were collected during the 10-day period that the Torpig botnet was under control.

All bots communicate with the Torpig command server through HTTP Post requests. This requests contains all the collected dat, as well as information about the bot. There are 8 different types of data that Torpig sends out: Mailbox account, email, form data, HTTP account, FTP account, POP account, and Windows passwords.

Attempting to analyze the size of the botnet is somewhat difficult. It can’t be done by merely checking how many IPs connect to the C&C server vecause of NAT and DHCP. However, Torpig contains information for hardware configurations and a mostly-unique ID for each bot. This led to an estimated 182,914 bots in the Torpig botnet. Further analysis was done to find the number of security researchers and search engine bots to get a more accurate number. Security researchers could be found by checking the default hardware configurations of VMWare and other virtualization tools. This gave a final estimate of 182,800 bots. In contrast, the number of IPs connecting to the C&C server was an order of magnitude larger. In the ten days the botnet was taken over, 49,924 new hosts were infected, though there were large spikes on two days.

Torpig is crafted to retrieve information that can easily be monetized. In the ten days, Torpig obtained 8310 accounts at financial institutions. 1660 credit and debit card numbers were also obtained. By pricing these accounts, the estimated value from these ten days is between $83K and $8.3M. In addition to information retrieval, Torpig opens proxies that can be used for spam or other activities, and represents a great deal of bandwidth that can be used in a DOS attack. It logs all other datas, which represents a huge breach of privacy and can be used to look at all chat, email, and other messages sent.

Analysis of the passwords retrieved showed that most were not very high strength, and roughly 28% of users reuse their passwords. This is evidence that the reason these botnets so large is a cultural problem, of people not understanding the consequences of irresponsible computer use.