Lisp in 96 lines of Python: Maxwells equations of software

September 30th, 2010

Peter Norvig has exquisite tastes in programming, is a Lisp guru and is also a great Python hacker. Put that together and what do you get?, an interpreter for the core of the Lisp dialect Scheme in 96 lines of Python. Norvig mentions Alan Kay’s view of Lisp as “Maxwell’s Equations of Software” in a 2004 interview with Stu Feldman:

SF: If nothing else, Lisp was carefully defined in terms of Lisp.

AK: Yes, that was the big revelation to me when I was in graduate school—when I finally understood that the half page of code on the bottom of page 13 of the Lisp 1.5 manual was Lisp in itself. These were “Maxwell’s Equations of Software!” This is the whole world of programming in a few lines that I can put my hand over.

There is also a companion essay, (How to Write a ((Better) Lisp) Interpreter (in Python)), that shows how to add other features, like macros, quasi-quote, tail recursion optimization and continuations. Sadly, this bloats the code to well over 200 lines.

Taintdroid catches Android apps that leak private user data

September 30th, 2010

Ars Technica has an an article on bad Android apps, Some Android apps caught covertly sending GPS data to advertisers.

“The results of a study conducted by researchers from Duke University, Penn State University, and Intel Labs have revealed that a significant number of popular Android applications transmit private user data to advertising networks without explicitly asking or informing the user. The researchers developed a piece of software called TaintDroid that uses dynamic taint analysis to detect and report when applications are sending potentially sensitive information to remote servers.

They used TaintDroid to test 30 popular free Android applications selected at random from the Android market and found that half were sending private information to advertising servers, including the user’s location and phone number. In some cases, they found that applications were relaying GPS coordinates to remote advertising network servers as frequently as every 30 seconds, even when not displaying advertisements. These findings raise concern about the extent to which mobile platforms can insulate users from unwanted invasions of privacy.”

TaintDroid is an experimental system that “analyses how private information is obtained and released by applications ‘downloaded’ to consumer phones”. A paper on the system will be presented at the 2010 USENIX Symposium on Operating Systems Design and Implementation later this month.

TaintDroid: An Information-Flow Tracking System for Realtime Privacy Monitoring on Smartphones, William Enck, Peter Gilbert, Byung-gon Chun, Landon P. Cox, Jaeyeon Jung, Patrick McDaniel, and Anmol N. Sheth, OSDI, October 2010.

The project, Realtime Privacy Monitoring on Smartphones has a good overview site with a FAQ and demo.

This is just one example of a rich and complex area full of trade-offs. We want our systems and devices to be smarter and to really understand us — our preferences, context, activities, interests, intentions, and pretty much everything short of our hopes and dreams. We then want them to use this knowledge to better serve us — selecting music, turing the ringer on and off, alerting us to relevant news, etc. Developing this technology is neither easy nor cheap and the developers have to profit from creating it. Extracting personal information that can be used or sold is one model — just as Google and others do to provide better ad placement on the Web.

Here’s a quote from the Ars Technical article that resonated with me.

“As Google says in its list of best practices that developers should adopt for data collection, providing users with easy access to a clear and unambiguous privacy policy is really important.”

We, and many others, are trying to prepare for the next step — when users can define their own privacy policies and these will be understood and enforced by their devices.

Banned Books Week

September 27th, 2010

The Banned Books Week (BBW) is an annual event that celebrates the “freedom to read”.  The campaign was started in 1982 and is held during the last week of September. The United States campaign, sponsored amongst others, by the American Library Association “highlights the benefits of free and open access to information while drawing attention to the harms of censorship by spotlighting actual or attempted bannings of books across the United States.” [1]

During this week, the Amnesty International directs attention to “the plight of individuals who are persecuted because of the writings that they produce, circulate or read”. [2]

The idea behind the event is to promote intellectual freedom: it encourages individuals to read books that have been challenged due to the unorthodox viewpoints expressed in these works of literature. Every year, the American Library Association’s Office for Intellectual Freedom records attempts by individuals and groups to ban books from libraries and classrooms. If you thought that censorship was a thing of the past, take a look at the Top Ten Most Frequently Challenged Books of 2009.  At-least 46 of the Radcliffe Publishing Course Top 100 Novels of the 20th Century have been targeted. The list includes acclaimed classics such as Catcher in the Rye, and To Kill a Mockingbird.

While some books are banned or restricted, a majority of them are not banned due to the efforts of librarians, booksellers, students, teachers, and the reading community at large. It is due to events like these that attention is drawn to the dangers of imposing restrictions on the availability of information in our world.

Is Stuxnet a cyber weapon aimed at an Iranian nuclear site?

September 23rd, 2010

There have been reports over the past weeks about Stuxnet, a new malware system that experts say is designed to seek out and damage certain kinds kind of industrial sites. Some argue that it has already hit and damaged its target.

The Christian Science Monitor published a good overview earlier this week.

“Cyber security experts say they have identified the world’s first known cyber super weapon designed specifically to destroy a real-world target – a factory, a refinery, or just maybe a nuclear power plant.

The cyber worm, called Stuxnet, has been the object of intense study since its detection in June. As more has become known about it, alarm about its capabilities and purpose have grown. Some top cyber security experts now say Stuxnet’s arrival heralds something blindingly new: a cyber weapon created to cross from the digital realm to the physical world – to destroy something.

At least one expert who has extensively studied the malicious software, or malware, suggests Stuxnet may have already attacked its target – and that it may have been Iran’s Bushehr nuclear power plant, which much of the world condemns as a nuclear weapons threat.”

The computer security company Symantec has been tracking it for a while and reported back in August that Stuxnet differs from typical Windows oriented in that it is designed to infect the Programmable Logic Controllers used in industrial control systems.

“As we’ve explained in our recent W32.Stuxnet blog series, Stuxnet infects Windows systems in its search for industrial control systems, often generically (but incorrectly) known as SCADA systems. Industrial control systems consist of Programmable Logic Controllers (PLCs), which can be thought of as mini-computers that can be programmed from a Windows system. These PLCs contain special code that controls the automation of industrial processes—for instance, to control machinery in a plant or a factory. Programmers use software (e.g., on a Windows PC) to create code and then upload their code to the PLCs.

Previously, we reported that Stuxnet can steal code and design projects and also hide itself using a classic Windows rootkit, but unfortunately it can also do much more. Stuxnet has the ability to take advantage of the programming software to also upload its own code to the PLC in an industrial control system that is typically monitored by SCADA systems. In addition, Stuxnet then hides these code blocks, so when a programmer using an infected machine tries to view all of the code blocks on a PLC, they will not see the code injected by Stuxnet. Thus, Stuxnet isn’t just a rootkit that hides itself on Windows, but is the first publicly known rootkit that is able to hide injected code located on a PLC.”

Symantec’s analysis of where Stuxnet has been found supports the theory that it was intended for targets in Iran, as the following map illustrates.

Security expert Frank Rieger writes that Stuxnet is exceptionally well designed and written and starts out on infected USB sticks.

“stuxnet is a so far not seen publicly class of nation-state weapons-grade attack software. It is using four different zero-day exploits, two stolen certificates to get proper insertion into the operating system and a really clever multi-stage propagation mechanism, starting with infected USB-sticks, ending with code insertion into Siemens S7 SPS industrial control systems. One of the Zero-Days is a USB-stick exploit named LNK that works seamlessly to infect the computer the stick is put into, regardless of the Windows operating system version – from the fossil Windows 2000 to the most modern and supposedly secure Windows 7.”

Rieger further argues that evidence suggests that Stuxnet is targeted not at Iran’s Bushehr reactor but at the uranium enrichment plant in Natanz and has already achieved success. To support the last conclusion, he sites a note on Wikileaks about a “a serious, recent, nuclear accident at Natanz” in July 2010.

Kodu: see apple red, move toward quickly

September 21st, 2010

The New York times has a short article, The 8-Year-Old Programmer, on Kodu, a programming environment intended to help young children learn to write programs.

“Kodu, built by a team at Microsoft’s main campus outside Seattle, is a programming environment that runs on an Xbox 360, using the game console’s controller rather than a keyboard. Instead of typing if/then statements in a syntax that must be memorized — as adult programmers do — the student uses the Xbox controller to pop up menus that contain options from which to choose. Kodu itself resembles a video game, with a point-and-click interface instead of the thousand-lines-of-text coding tools used by grown-ups.”

You can also read about Kodu in the Wikipedia article Kodu Game Lab or Kodu project page at Microsoft Research, from which you can also download a free version for the PC.

Kodu is an rule-based, event-driven language with a simple context free grammar that lets you write rules like “see apple red, move toward quickly”.

Kudu takes it’s place in a long history of programming languages developed to teach programming to children, starting with Logo in the late 1960s. None of these have ever truly caught on, although Logo was taught in many elementary schools in the 1980s. As a computer scientist, I believe that being able to write simple programs for one’s own use will eventually be a skill that all educated people will have, just as being able to basic numerical computations and write effective text are today.

Nominate books for the 2011 UMBC New Student Book Experience

September 20th, 2010

Read a good book lately? Why not nominate it for the 2011 UMBC New Student Book Experience, which invites new UMBC students to read the selected book and engage in formal and informal discussions about it as the new year starts.

We are looking for books that (1) are compelling, intellectually stimulating, engaging on multiple levels and capable of generating interesting discussions; (2) address issues meaningful to students of diverse backgrounds; (3) are not widely required in Maryland high schools or made into a recent film; and (4) are available in paperback and not overly long.

You can nominate one or more using this handy Facebook app. The app uses the Google Books API to help identify books given a partial title, so it’s easy to use. After recoding your nomination, you’ll have an opportunity to make an optional post to your Facebook page like the one below, so your friends can see what you suggested. Nominations will close on October 31, 2010 and the selection will be announced in the Spring.

Nominate a book for the 2011 UMBC New Student Book Experience

UMBC Linux Users Group Installfest, Fri 9/24/2010,The Commons

September 20th, 2010

Got Linux? Let your computer know who is boss! The UMBC Linux Users Group (LUG) is holding a Linux Installfest from 10:30am to 4:30pm on Friday 24 September in the Main Street concourse of the UMBC Commons. Bring your computer and the LUG experts will help you install Linux on it in addition to your current operating system.

An agent-based model of the peer-review process

September 19th, 2010

The peer review process is central to most research disciplines and is used in the selection of papers for publication and research proposals for funding.

A new paper by Stefan Thurner and Rudolf Hanel develops an agent-based model of the scientific peer review process, Peer-review in a world with rational scientists: Toward selection of the average.

“… we are interested in the effects of rational referees, who might not have any incentive to see high quality work other than their own published or promoted. We find that a small fraction of incorrect (selfish or rational) referees can drastically reduce the quality of the published (accepted) scientific standard. We quantify the fraction for which peer review will no longer select better than pure chance. Decline of quality of accepted scientific work is shown as a function of the fraction of rational and unqualified referees. We show how a simple quality-increasing policy of e.g. a journal can lead to a loss in overall scientific quality, and how mutual support-networks of authors and referees deteriorate the system.”

Their agent model has several reviewers types:

  • The correct: Accepts good and rejects bad papers.
  • The stupid: This referee can not judge the quality of a paper (e.g. because of incompetence or lack of time) and takes a random decision on a paper.
  • The rational: The rational referee knows that work better than his/her own might draw attention away from his/her own work. For him there is no incentive to accept anything better than one’s own work, while it might be fine to accept worse quality.
  • The altruist: Accepts all papers.
  • The misanthropist: Rejects all papers.

I’ve known them all, as I am sure many of us have. As an editor or program chair I’ve met a few other types, including these:

  • The Bartleby: His or her response to an invitation is always “I would prefer not to.”
  • The Black Hole: Messages go in and nothing ever comes out.
  • The Gary Cooper: A person of few words, even when many are called for.
  • The Perseverator: Sees all sides of any decision and keeps all carefull in balance. Usually recommends “major revision”.

I am sure I’ve overlooked some — suggest your own via a comment.

(h/t Shlomo Argamon)

Proofiness: when mathematics turns to the dark side

September 18th, 2010

This sounds like a book worth reading, Proofiness – The Dark Arts of Mathematical Deception by Charles Seife. It is reviewed in tomorrow’s New York Times — Fibbing With Numbers.

It goes without saying that what you learn in a book like this should only be used for defensive purposes. Do not turn to the Dark Side!

The book reminds me of the classic How to Lie with Statistics published in the 1950s.

Smart phones recognize users gait

September 16th, 2010

Technology review has a short article on new work on doing gait analysis with the accelerometers built into many smart phones, Smart Phones that Know Their Users by How They Walk. The results are from the following paper:

Mohammad O. Derawi, Claudia Nickel, Patrick Bours and Christoph Busch, Unobtrusive User-Authentication on Mobile Phones using Biometric Gait Recognition, The Sixth International Conference on Intelligent Information Hiding and Multimedia Signal Processing, Darmstadt, 15-17 October 2010.

Abstract: The need for more security on mobile devices is increasing with new functionalities and features made available. To improve the device security we propose gait recognition as a protection mechanism. Unlike previous work on gait recognition, which was based on the use of video sources, floor sensors or dedicated high-grade accelerometers, this paper reports the performance when the data is collected with a commercially available mobile device containing low-grade accelerometers. To be more specific, the used mobile device is the Google G1 phone containing the AK8976A embedded accelerometer sensor. The mobile device was placed at the hip on each volunteer to collect gait data. Preproccesing, cycle detection and recognition-analysis were applied to the acceleration signal. The performance of the system was evaluated having 51 volunteers and resulted in an equal error rate (EER) of 20%.

The potential application is that a phone could recognize that it may have been stolen if it is being carried by a person with a different gait. I guess it would then phone home with it’s location, not unlike the golden harp in some version of Jack in the Beanstalk.

The accuracy would have to be improved to make this practical, of course, and it might not be a killer app, but it is a good example of how passive sensing by smart phones can acquire useful context information.

Call for bids to host AAMAS-2013

September 16th, 2010

This is a call for bids to host the Twelfth International Conference on Autonomous Agents and Multiagent Systems (AAMAS) in 2013. Bids will be considered from all geographical regions; however, for the 2013 conference, we particularly encourage bids from the Americas.

Bids are sought from volunteers from the scientific community, though they may be supported by paid meeting professionals.

All correspondence regarding bids should be directed by email to the IFAAMAS Conference Committee Chair (Munindar P. Singh, and Chair Elect (Onn Shehory,

Bids should be made by individuals or small groups, with the backing of a host institution, typically a university or research center. Groups or individuals who are planning to submit a bid should notify Drs. Singh and Shehory of their intention as soon as possible.

  • Now: Expression of interest and queries
  • November 17, 2010: Submission of final bid
  • November 18, 2010-February 28, 2011: Potential discussions with bidders; internal discussions in the IFAAMAS Board
  • March 1, 2011: Decision

See the full AAMAS-2013 call for bids for more information

Zuck opens up

September 13th, 2010

Jose Antonio Vargas profiles Mark Zuckerberg in this week’s New Yorker in The Face of Facebook, Mark Zuckerberg opens up. It’s a short piece, but I learned a few facts. One in fourteen people in the world has a Facebook account. All of Zuckerberg’s acquaintances call him Zuck. Zuck has eight hundred and seventy-nine Facebook friends. Zuck likes Ender’s Game and roasting goats. He considers himself an “awkward person”. Not mentioned in the article, but of possible interest, is that The Social Network opens on October 1.