EDITOR'S EYE

The World of Software Development.

November 2007

Day 2 of CSDN-Dr. Dobb's Software Development 2.0 conference is a done deal. A wrap. Stick a fork in it--it's done. And hoping I don't get hurt patting myself on the back, it really was a great conference and a marvelous experience. Actually, I'm not worried about hurting myself, because I really didn't do much besides show up and look pretty. Granted, I did have one speaking session, but the accolades go to the folks at CSDN and the great crew of great speakers.

Here's what surprised me the most about the two-day event: Some of the most technically challenging presentations drew the biggest crowds and generated the most audience participation. For instance, Andrei Alexandrescu's session on "Lock-Free Programming" as it pertains to parallelization is a topic for the not-faint-of-heart. Moreover, it was the last session of the conference. And it was packed by more than 200 people who wouldn't stop asking questions. When Andrei said "final question" for the fifth time, well, I wanted to remind him that I was hungry and the official "last dinner" for the event was getting cold.

Andrei's experience matched that of James Reinders when a crowd filled the room to learn about "Thinking Parallel", a topic that several speakers touched on over the two days. Again, audience questions were top-flight and non-stop. The only real difference was that I had eaten lunch that day, but not the day of Andrei's presentation.

One session that I really enjoyed was that of Jonathan Palley, the VP of technology at Idapted which is using Ruby on Rails to build an international VoIP and interactive web platform. Not only did Jonathan provide a fascinating snapshot of the power of RoR, but did so in a mesmerizing fashion while sharing insights into what programmers ought to be doing more of (iteration) and less of (worrying about ugly code at the outset of development).

One real nuisance of all conferences that have parallel tracks is when two sessions that you want to attend are presented at the same time. That's why I missed Tenni Theurer's "Building High-Performance Web Sites" which by all accounts was a killer. Alas, that was probably the case with others too.

So at this point, there are only three Beijing-related concerns on my mind:

1. Can the traffic to the airport possibly match the traffic from the airport?
2. How can you sleep for 12 hours in coach class?
3. How is it possible to leave Beijing at 1:00 PM on Saturday and arrive in Seattle at 1:00 PM the same Saturday?

Oh well, I have a year to mull over these questions until next year back in Beijing.

Posted by Jon Erickson at 09:30 AM  Permalink |

So I arrived in China in fine shape--well, as fine as you can be after a 14-hour plane trip in economy class--to participate in CSDN-Dr. Dobb's Software Development 2.0 conference in Beijing.

Luckily, the fine folks at CSDN had a ride waiting for me. But what the ride didn't have -- but could have used -- was a project that engineers at the U.S. National Institute of Standards and Technology (NIST) have developed -- IVBSS, a laser-based ranging system to assess the performance of automobile collision warning systems.

Not that we needed it, I think the driver was telling me. ("I think" because I don't speak Chinese -- yet.) But he was quite calm and it seemed perfectly normal to him that two cars traveling in opposite directions at relatively high speeds should be vying for the same road space. After all, it was rush hour. Not that traffic is anymore chaotic in Beijing than in San Francisco, but it did seem that someone was going the wrong way on a one-way street at just about every turn.

Still, he might have been correct, at least by U.S. standards. According to the U.S. Department of Transportation, there are 3.6 million rear-end, road departure and lane change crashes that occur each year in the U.S., which is why NIST engineers are working on advaned Integrated Vehicle-Based Safety Systems (IVBSS) with the goal of reducing such collisions by 48 percent.

The NIST system consists of a camera and microphone in the vehicle's cab that detect the driver's warning, a suite of calibrated cameras to measure the distance to lane boundaries, and laser scanners to measure the distance to obstacles forward and to the side of the vehicle. The NIST system can detect an object to within about 4/5 of a meter from up to 60 meters away at speeds up to 25 m/s (within 33 inches at a distance of 197 feet and speeds up to 56 mph.)

The Department of Transportation is going to equip 20 automobiles and 10 trucks with the the IVBSS warning system. If they need test vehicles, there's no lack of them here in Beijing.

Posted by Jon Erickson at 08:36 PM  Permalink |

In Greek mythology, dryads were tree nymphs -- female deities that hung out in the woods. Since then, dryads have popped up in literature (C.S. Lewis's "The Chronicles of Narnia"), computer games (World of Warcraft), and even TV shows (Xena: Warrior Princess and Scooby-Do). And now their latest incarnation is as a development environment for concurrent programming.

More specifically, Dryad is an infrastructure out of Microsoft Research designed to help programmers access the resources of thousands of machines without knowing anything about concurrent programming.

The goal of the Dryad project, according to senior researcher Michael Isard, "is to abstract away a lot of the practical details of the cluster -- the data placement, the network hierarchy, the strategy for fault tolerance -- so that the programmer can work at a higher level and concentrate more on the structure of the computation and rely on Dryad to do the scheduling, the fault tolerance, and those kinds of things."

In Dryad: Distributed Data-Parallel Programs from Sequential Building Blocks, a paper written by Isard, Mihai Budiu, Yuan Yu, Andrew Birrell, and Dennis Fetterly, the researchers explain:

The Dryad execution engine handles all the difficult problems of creating a large, distributed, concurrent application: scheduling the use of computers and their CPUs, recovering from communication or computer failures, and transporting data between [computation] vertices.

Moreover, say the authors, Dryad is designed to scale effectively, from a single, multicore computer to small clusters of computers to datacenters with thousands of computers.

One thing that's particularly interesting is the team has leveraged non-research oriented Microsoft technologies to extend Dryad. For instance, the researches have rolled out DryadLINQ which combines Dryad and .NET's LINQ. Dryad takes care of the distributed for parallel applications, while LINQ lets you write and debug applications in a SQL-like query language in a familiar environment like Visual Studio.

"Dryad takes away the programmer’s need to understand low-level concurrency, but it still relies on the programmer to think at some level of abstraction about how the job could be divided up," explains Isard. "Programmers don’t have to worry about low-level synchronization primitives, but they do still have to understand something about the structure of what needs to be done and what depends on what else."

All in all, Dryad sound interesting and important, especially as the need for tools that enable concurrency accelerates.

-- Jonathan Erickson
jerickson@ddj.com

Posted by Jon Erickson at 09:14 AM  Permalink |

Over the years, Dr. Dobb's has published a number of articles about traffic signals. Let's see, there was Extended State Diagrams and Reactive Systems and Visually Designing Embedded-Systems Applications, both by Doron Drusinsky. Then there was The Halting Problem by Ed Nisley. And Ala Qumsieh wrote Fuzzy Logic in Perl for The Perl Journal and touched on traffic signals.

Now the authors didn't write these articles, and we didn't publish them, because we're a bunch of caffine-stoked, Type A personalities who hate sitting in the car waiting for the traffic light to change. No, we're all laid back Type whatevers who like an intellectual challenge -- and traffic signal systems are great for this. Moreover, as we're learning these days, efficient traffic signal systems are really important in terms of energy consumption and the environment.

For instance, according to Dirk Helbing, a Professor of Sociology at the ETH Zurich Chair of Sociology, traffic flows account for up to one-third of global energy consumption -- so efficiently managing traffic flow can significantly reduce waste and lower harmful emissions. Consequently, Helbing and Stefan Lammer of the Institute for Transport and Economics at Dresden University of Technology, are proposing propose a self-organized control system for traffic lights to improve vehicular traffic flow.

The first problem, says Helbing, is that most systems are antiquated. Traffic lights are optimized for pre-established assumptions, and not for real time. Plus there was far less traffic when the systems were installed. To deal with this, the solution has been to simply install more lights. However, says Helbing, "even for normal-sized cities, supercomputers are just not fast enough to compute all of the different options that exist for controlling traffic lights. So the number of choices actually considered by the optimization program is significantly reduced." He goes on to say that "the variation in the number of vehicles that queue up at a traffic light at any minute of the day is huge, and you are optimizing for a situation that basically is true on average but that is never true for any single day or minute: essentially for a situation that never exists. Plus, even adaptive traffic lights in modern control schemes are usually restricted to a variation of cycle-based control."

What Helbing and Lammer propose is an optimized decentralized system that makes travel time more predictable, though traffic light sequence less so. Along with the optimization, they add a stabilizing strategy. Interestingly, by themselves each strategy -- optimization and stabilization -- underperformed. But when properly combined, the approaches performed great at controlling traffic at all volume levels.

Simulations they ran went well with non-periodic traffic lights releasing long traffic lines, making travel time more predictable. Fuel consumption and C02 emissions also went down.

Of course, all this would be a far less problem if we all were riding motor scooters :-)

-- Jonathan Erickson
jerickson@ddj.com

Posted by Jon Erickson at 11:29 AM  Permalink |

It doesn't seem fair! How are schmucks like me supposed to go up against researchers from AT&T Labs and win anything? Here's what happened.

Netlfix, the online movie rental service, has a contest called the NetflixPrize with the goal of improving the accuracy of predictions about how much someone is going to like a movie, based on the viewer's movie preferences. And one prize was $50,000, which would keep me in lattes for the forseeable future.

So my algorithm went something like this: "If movie stars Sandra Bullock, then movie is bad. If movie stars Franka Potente, then movie is good -- really good."

Apparently that wasn't good enough for the folks at Netflix. I guess they wanted more details, which was what Team KorBell, a group of researchers at AT&T Labs Research, provided. Team KorBell consisted of Yehuda Koren, Robert Bell, and Chris Volinsky, who in their day job work on visualizing and analyzing large networks for AT&T. So right away you can probably guess they had an edge on me. Team KorBell improved upon the Netflix recommendation system by 8.43 percent -- the best score for the competition in which more than 27,000 contestants on more than 2,550 teams from 161 countries participated.

I won't go into the details of Team KorBell's solution. I'm too disgusted, and don't understand it anyway. However, you might want to take a look at their paper The BellKor Solution to the Netflix Prize. Let's just say that they included a lot more math than I did, and a whole bunch of equations and graphs. But supposedly it works.

Just to show that I'm not a sore loser, I'd like to say congratulations to Yehuda Koren, Robert Bell, and Chris Volinsky.

They may have walked away with the $50K, but the $1 million Grand Prize is still up for grabs and all I have to do is tweak my algorithm a bit -- say "Britney Spears = bad movie"?

-- Jonathan Erickson
jerickson@ddj.com

Posted by Jon Erickson at 11:36 AM  Permalink |

A new security vulnerability in Windows 2000 that lets intruders access information sent from the computer--even information no longer stored on the computer--has been reported. According to the claim, the problem is with Windows' random-number generator. To date, the researchers have only tested Windows 2000, but they're guessing that newer versions (such as Windows XP and Vista) have similar vulnerabilities since they use similar random-number generators.

In their analysis, University of Hafia computer science professor Benny Pinkas, along with Hebrew University grad students Zvi Gutterman and Leo Dorrendorf, reengineerd the algorithm (the CryptGenRandom function) used by the pseudo-random number generator: Given the internal state of the generator, the previous state can be computed in $O(2^{23})$ work (this is an attack on the forward-security of the generator, an $O(1)$ attack on backward security is trivial). The attack on forward-security demonstrates that the design of the generator is flawed, since it is well known how to prevent such attacks. They also analyzed how the generator is run by the operating system, and found that it amplifies the effect of the attacks.

In their paper Cryptanalysis of the Windows Random Number Generator, the reseachers said that the implication of these findings is that a buffer overflow attack or a similar attack can be used to learn a single state of the generator, which can then be used to predict all random values, such as SSL keys, used by a process in all its past and future operation.

"There is no doubt that hacking into a computer using our method requires advanced planning. On the other hand, simpler security breaches also require planning," said Pikas, "and I believe that there is room for concern at large companies, or for people who manage sensitive information using their computers, who should understand that the privacy of their data is at risk."

Posted by Jon Erickson at 11:38 AM  Permalink |

It probably comes as no surprise that the Secure Hash Algorithm (SHA) isn't as secure as it used to be or as secure as it needs to be. Through no fault of its own, of course. It's those darn security attacks by intruders, some malicious, that have led security experts to question the security of current SHA implementations--SHA-0, SHA-1, and SHA-2.

Consequently, the National Institute of Standards and Technology (NIST) has opened a competition to develop SHA-3. The competition is NIST’s response to recent advances in the analysis of hash algorithms. The new hash algorithm will augment the hash algorithms currently specified in the Federal Information Processing Standard (FIPS) 180-2, Secure Hash Standard. NIST’s goal is that SHA-3 provide increased security and offer greater efficiency for the applications using cryptographic hash algorithms. FIPS standards are required for use in federal civilian computer systems and are often adopted voluntarily by private industry.

FIPS 180-2 specifies five cryptographic hash algorithms, including SHA-1 and the SHA-2 family of hash algorithms. Because serious attacks have been reported in recent years against cryptographic hash algorithms, including SHA-1, and because SHA-1 and the SHA-2 family share a similar design, NIST is standardizing an additional hash algorithm to augment those currently specified in FIPS 180-2.

The competition announcement specifies the submission requirements, the minimum acceptability requirements, and the evaluation criteria for candidate hash algorithms. Entries for the competition must be received by October 31, 2008.

For background on SHA, some reference points include:

• Keeping Sensitive Data Safe
• Principles and Performance of Cryptographic Algorithms
• The Mithra Authentication Protocol
• RSA Digital Signatures
• Good Hash Tables and Multiple Hash Functions
• Cryptanalysis of SHA-1

Posted by Jon Erickson at 08:58 AM  Permalink |

After traveling through India and Russia with David Katch earlier this year, I ended up with the misperception that the only things happening at University of Michigan involved football and basketball. But as it turns out, there's more than sports going in Ann Arbor, particularly when it comes to engineering.

For instance, what engineering researchers at the university have come up with is a technique to automate post-silicon debugging. That is, they've developed a way to fix design bugs and wrong wire connections in computer chips after they've been fabricated in silicon.

The methodolgy, called FogClear, is a debugging technique that repairs some electrical errors while preserving functional correctness. FogClear uses puzzle-solving search algorithms to diagnose problems early on and automatically adjust the blueprint for the chip.

According to Kai-Hui Chang, who along with professors Igor Markov and Valeria Bertacco developed the methodolgy, "bugs found post-silicon are often very difficult to diagnose and repair because it is difficult to monitor and control the signals that are buried inside a silicon die, or chip. Up until now engineers have handled post-silicon debugging more as an art than a science."

FogClear automates this process by searching for and finding the simplest way to fix a bug that has the least impact on the working parts of the chip. The solution usually requires reconnecting certain wires, and does not affect transistors.

And after a rocky start says David, the football team isn't doing too badly either.

Posted by Jon Erickson at 12:09 PM  Permalink |

According to the results of a report designed to identify current open source adoption rates and trends in the Federal government and undertaken by the Federal Open Source Alliance, the Feds seem to have a growing appetite of and appreciation for open source.

Based on a survey of Department of Defense (DoD), Federal civilian, and Intelligence IT executives, the study entitled "Federal Open Source Referendum" indicates that Federal open source implementers and non-implementers have different perceptions of the benefits and challenges associated with deploying open source, most notably around security issues. Agencies that have implemented open source say that advanced security is the biggest benefit -- 30 percent cite access to advanced and multi-leveled security capabilities as the top benefit -- while those which have not implemented cite security as a top challenge -- 40 percent.

Those that have adopted open source go on to identify other key open source benefits, including data center consolidation (17 percent), the ability to customize applications (17 percent), and the ability to facilitate cross-system or cross-agency application/process sharing (12 percent). Only 9 percent of Feds implementing open source cite cost savings as the primary benefit.

Some 55 percent of respondents note that they have been or are involved in open source implementations and 90 percent of those respondents assert that the deployment has benefited their agency. Drilling down, 97 percent of Feds -- Federal civilian, DoD, and Intelligence -- characterize their open source deployments as successful or partially successful. Only three percent of Federal civilian and DoD respondents respectively consider their deployments failures.

Overall, 90 percent of open source respondents who have adopted open source assert that their agency derives value from it. 29 percent of the respondents who have not implemented open source say that they plan to implement it in the next six to 12 months, with the Intelligence community leading the way.

The study (available at www.federalopensourcealliance.com) is based on an online survey of 218 Federal civilian, DoD, and Intelligence agency IT decision makers. The Federal Open Source Alliance is supported by Hewlett-Packard, Intel, and Red Hat.

Posted by Jon Erickson at 11:39 AM  Permalink |