Tag Archives: algorithm

Better debugger

System to automatically find a common type of programming bug significantly outperforms its predecessors.

By Larry Hardesty

CAMBRIDGE, Mass. – Integer overflows are one of the most common bugs in computer programs — not only causing programs to crash but, even worse, potentially offering points of attack for malicious hackers. Computer scientists have devised a battery of techniques to identify them, but all have drawbacks.

This month, at the Association for Computing Machinery’s International Conference on Architectural Support for Programming Languages and Operating Systems, researchers from MIT’s Computer Science and Artificial Intelligence Laboratory (CSAIL) will present a new algorithm for identifying integer-overflow bugs. The researchers tested the algorithm on five common open-source programs, in which previous analyses had found three bugs. The new algorithm found all three known bugs — and 11 new ones.

The variables used by computer programs come in a few standard types, such as floating-point numbers, which can contain decimals; characters, like the letters of this sentence; or integers, which are whole numbers. Every time the program creates a new variable, it assigns it a fixed amount of space in memory.

If a program tries to store too large a number at a memory address reserved for an integer, the operating system will simply lop off the bits that don’t fit. “It’s like a car odometer,” says Stelios Sidiroglou-Douskos, a research scientist at CSAIL and first author on the new paper. “You go over a certain number of miles, you go back to zero.”

In itself, an integer overflow won’t crash a program; in fact, many programmers use integer overflows to perform certain types of computations more efficiently. But if a program tries to do something with an integer that has overflowed, havoc can ensue. Say, for instance, that the integer represents the number of pixels in an image the program is processing. If the program allocates memory to store the image, but its estimate of the image’s size is off by several orders of magnitude, the program will crash.

Charting a course

Any program can be represented as a flow chart — or, more technically, a graph, with boxes that represent operations connected by line segments that represent the flow of data between operations. Any given program input will trace a single route through the graph. Prior techniques for finding integer-overflow bugs would start at the top of the graph and begin working through it, operation by operation.

For even a moderately complex program, however, that graph is enormous; exhaustive exploration of the entire thing would be prohibitively time-consuming. “What this means is that you can find a lot of errors in the early input-processing code,” says Martin Rinard, an MIT professor of computer science and engineering and a co-author on the new paper. “But you haven’t gotten past that part of the code before the whole thing poops out. And then there are all these errors deep in the program, and how do you find them?”

Rinard, Sidiroglou-Douskos, and several other members of Rinard’s group — researchers Eric Lahtinen and Paolo Piselli and graduate students Fan Long, Doekhwan Kim, and Nathan Rittenhouse — take a different approach. Their system, dubbed DIODE (for Directed Integer Overflow Detection), begins by feeding the program a single sample input. As that input is processed, however — as it traces a path through the graph — the system records each of the operations performed on it by adding new terms to what’s known as a “symbolic expression.”

“These symbolic expressions are complicated like crazy,” Rinard explains. “They’re bubbling up through the very lowest levels of the system into the program. This 32-bit integer has been built up of all these complicated bit-level operations that the lower-level parts of your system do to take this out of your input file and construct those integers for you. So if you look at them, they’re pages long.”

Trigger warning

When the program reaches a point at which an integer is involved in a potentially dangerous operation — like a memory allocation — DIODE records the current state of the symbolic expression. The initial test input won’t trigger an overflow, but DIODE can analyze the symbolic expression to calculate an input that will.

The process still isn’t over, however: Well-written programs frequently include input checks specifically designed to prevent problems like integer overflows, and the new input, unlike the initial input, might fail those checks. So DIODE seeds the program with its new input, and if it fails such a check, it imposes a new constraint on the symbolic expression and computes a new overflow-triggering input. This process continues until the system either finds an input that can pass the checks but still trigger an overflow, or it concludes that triggering an overflow is impossible.

If DIODE does find a trigger value, it reports it, providing developers with a valuable debugging tool. Indeed, since DIODE doesn’t require access to a program’s source code but works on its “binary” — the executable version of the program — a program’s users could run it and then send developers the trigger inputs as graphic evidence that they may have missed security vulnerabilities.

Source: News Office

Software that knows the risks

Planning algorithms evaluate probability of success, suggest low-risk alternatives.

By Larry Hardesty

CAMBRIDGE, Mass. – Imagine that you could tell your phone that you want to drive from your house in Boston to a hotel in upstate New York, that you want to stop for lunch at an Applebee’s at about 12:30, and that you don’t want the trip to take more than four hours. Then imagine that your phone tells you that you have only a 66 percent chance of meeting those criteria — but that if you can wait until 1:00 for lunch, or if you’re willing to eat at TGI Friday’s instead, it can get that probability up to 99 percent.

That kind of application is the goal of Brian Williams’ group at MIT’s Computer Science and Artificial Intelligence Laboratory — although the same underlying framework has led to software that both NASA and the Woods Hole Oceanographic Institution have used to plan missions.

At the annual meeting of the Association for the Advancement of Artificial Intelligence (AAAI) this month, researchers in Williams’ group will present algorithms that represent significant steps toward what Williams describes as “a better Siri” — the user-assistance application found in Apple products. But they would be just as useful for any planning task — say, scheduling flights or bus routes.

Together with Williams, Peng Yu and Cheng Fang, who are graduate students in MIT’s Department of Aeronautics and Astronautics, have developed software that allows a planner to specify constraints — say, buses along a certain route should reach their destination at 10-minute intervals — and reliability thresholds, such as that the buses should be on time at least 90 percent of the time. Then, on the basis of probabilistic models — which reveal data such as that travel time along this mile of road fluctuates between two and 10 minutes — the system determines whether a solution exists: For example, perhaps the buses’ departures should be staggered by six minutes at some times of day, 12 minutes at others.

If, however, a solution doesn’t exist, the software doesn’t give up. Instead, it suggests ways in which the planner might relax the problem constraints: Could the buses reach their destinations at 12-minute intervals? If the planner rejects the proposed amendment, the software offers an alternative: Could you add a bus to the route?

Short tails

One aspect of the software that distinguishes it from previous planning systems is that it assesses risk. “It’s always hard working directly with probabilities, because they always add complexity to your computations,” Fang says. “So we added this idea of risk allocation. We say, ‘What’s your budget of risk for this entire mission? Let’s divide that up and use it as a resource.’”

The time it takes to traverse any mile of a bus route, for instance, can be represented by a probability distribution — a bell curve, plotting time against probability. Keeping track of all those probabilities and compounding them for every mile of the route would yield a huge computation. But if the system knows in advance that the planner can tolerate a certain amount of failure, it can, in effect, assign that failure to the lowest-probability outcomes in the distributions, lopping off their tails. That makes them much easier to deal with mathematically.

At AAAI, Williams and another of his students, Andrew Wang, have a paper describing how to evaluate those assignments efficiently, in order to find quick solutions to soluble planning problems. But the paper with Yu and Fang — which appears at the same conference session — concentrates on identifying those constraints that prevent a problem’s solution.

There’s the rub

Both procedures are rooted in graph theory. In this context, a graph is a data representation that consists of nodes, usually depicted as circles, and edges, usually depicted as line segments connecting the nodes. Any scheduling problem can be represented as a graph. Nodes represent events, and the edges indicate the sequence in which events must occur. Each edge also has an associated weight, indicating the cost of progressing from one event to the next — the time it takes a bus to travel between stops, for instance.

Yu, Williams, and Fang’s algorithm first represents a problem as a graph, then begins adding edges that represent the constraints imposed by the planner. If the problem is soluble, the weights of the edges representing constraints will everywhere be greater than the weights representing the costs of transitions between events. Existing algorithms, however, can quickly home in on loops in the graph where the weights are imbalanced. The MIT researchers’ system then calculates the lowest-cost way of rebalancing the loop, which it presents to the planner as a modification of the problem’s initial constraints.

Source: MIT News Office

Amazon's delivery drones. Credit: Amaon

Making drones more customizable

Airware’s operating system makes drones simple to build and modify for multiple applications.

By Rob Matheson 

A first-ever standard “operating system” for drones, developed by a startup with MIT roots, could soon help manufacturers easily design and customize unmanned aerial vehicles (UAVs) for multiple applications.

Today, hundreds of companies worldwide are making drones for infrastructure inspection, crop- and livestock-monitoring, and search-and-rescue missions, among other things. But these are built for a single mission, so modifying them for other uses means going back to the drawing board, which can be very expensive.

Now Airware, founded by MIT alumnus Jonathan Downey ’06, has developed a platform — hardware, software, and cloud services — that lets manufacturers pick and choose various components and application-specific software to add to commercial drones for multiple purposes.

The key component is the startup’s Linux-based autopilot device, a small red box that is installed into all of a client’s drones. “This is responsible for flying the vehicle in a safe, reliable manner, and acts as hub for the components, so it can collect all that data and display that info to a user,” says Downey, Airware’s CEO, who researched and built drones throughout his time at MIT.

To customize the drones, customers use software to select third-party drone vehicles and components — such as sensors, cameras, actuators, and communication devices — configure settings, and apply their configuration to a fleet. Other software helps them plan and monitor missions in real time (and make midflight adjustments), and collects and displays data. Airware then pushes all data to the cloud, where it’s aggregated and analyzed, and available to designated users.

If a company decides to use a surveillance drone for crop management, for instance, it can easily add software that stitches together different images to determine which areas of a field are overwatered or underwatered. “They don’t have to know the flight algorithms, or underlying hardware, they just need to connect their software or piece of hardware to the platform,” Downey says. “The entire industry can leverage that.”

Clients have trialed Airware’s platform over the past year — including researchers at MIT, who are demonstrating delivery of vaccines in Africa. Delta Drone in France is using the platform for open-air mining operations, search-and-rescue missions, and agricultural applications. Another UAV maker, Cyber Technology in Australia, is using the platform for drones responding to car crashes and other disasters, and inspecting offshore oilrigs.

Now, with its most recent $25 million funding round, Airware plans to launch the platform for general adoption later this year, viewing companies that monitor crops and infrastructure — with drones that require specific cameras and sensors — as potential early customers.

A company from scratch

Airware’s roots date to 2005, when Downey, who studied electrical engineering and computer science, organized an MIT student team — including Airware’s chief technology officer, Buddy Michini ’07, SM ’09, PhD ’13 — to build drones for an intercollegiate competition.

At the time, drones were primarily used for military surveillance, powered by a “black box” that could essentially fly the drones and control the camera. There were also a handful of open-source projects — made by hobbyists — that let people modify drones, but the code was unreliable when tweaked. “If you wanted to do anything novel, your hands were tied,” Downey says.

The group’s decision: build a drone from scratch. But their advisor, Jonathan How, a professor of aeronautics and astronautics who directs of the Aerospace Controls Laboratory, told them that required too much time, and would cost them the competition.

“We said, ‘You’re right, but we’re MIT students, and we’d feel better getting last place and learning a lot doing it than winning the competition by repackaging a black-box solution,’” Downey says.

Sure enough, the team earned second-to-last place. “But we learned that black-box solution didn’t work if you’re trying to address new applications, and the open-source wasn’t reliable even though you could change the software,” Downey says.

A five-year stretch at Boeing — as an engineer for the U.S. military’s A160 Hummingbird UAV and as a commercial pilot — put Downey in contact with drone manufacturers, who, he found, were still using black boxes or open-source designs.

“They were basically facing the same challenges we faced as undergrads at MIT,” Downey says. Thus Airware was born in 2010 — first run only by Downey, then with Michini and a team of Boeing engineers — to make a military-grade “black box” system, but whose capabilities could be tweaked and extended.

Early prototypes were trialed by How’s group at MIT, before Airware entered two California incubators, Lemnos Labs and Y-Combinator, in 2013. Since then, they’ve raised $40 million from investors and expanded their team from five to more than 50 employees. “The last 18 months has been a rapid rise,” Downey says.

Not much of the early MIT drone designs made it into the final Airware platform. “But building that early drone at MIT, and having the idea to leverage an enterprise-grade platform that you can extend the capabilities of, very directly became what Airware is today,” Downey says.

“The DOS for drones”

Today, Downey says, the development of a standard operating system for drones is analogous to Intel processors and Microsoft’s DOS paving the way for personal computers in the 1980s. Before those components became available, hobbyists built computers using software that didn’t work with different computers. At the same time, powerful mainframes were only available to a select few — and still suffered software-incompatibility issues.

Then came Intel’s processors and DOS. Suddenly, engineers could build computers around the standard processor and create software on the operating system, without needing to know details of the underlying hardware.

“We’re doing the same thing for the drone space,” Downey says. “There are 600 companies building differing versions of drone hardware. We think they need the Intel processor of the drones, if you will, and that operating system-level software component, too — like the DOS for drones.”

The benefits are far-reaching, Downey says: “Drone companies, for instance, want to build drones and tailor them for different applications without having to build everything from scratch,” he says.

But companies developing cameras, sensors, and communication links for drones also stand to benefit, he adds, as their components will only need to be compatible with a single platform.

Additionally, it could help the Federal Aviation Administration (FAA) better assess the reliability of drones; Congress recently tasked the agency with compiling UAV rules and regulations by 2015. This could also help promote commercial drone use in the United States, which lags behind other countries around the world, primarily in Europe, Downey says.

“Rather than see a world where there’s 500 drones flying overhead, and every drone has different software and electronics, it’s good for the FAA if all of them had reliable and common hardware and software,” he says. “We think it’s valuable for everybody.”

Source: MIT News

Amazon's delivery drones. Credit: Amaon

Delivery by drone

New algorithm lets drones monitor their own health during long package-delivery missions.

By Jennifer  Chu

CAMBRIDGE, MA — In the near future, the package that you ordered online may be deposited at your doorstep by a drone: Last December, online retailer Amazon announced plans to explore drone-based delivery, suggesting that fleets of flying robots might serve as autonomous messengers that shuttle packages to customers within 30 minutes of an order.

To ensure safe, timely, and accurate delivery, drones would need to deal with a degree of uncertainty in responding to factors such as high winds, sensor measurement errors, or drops in fuel. But such “what-if” planning typically requires massive computation, which can be difficult to perform on the fly.

Now MIT researchers have come up with a two-pronged approach that significantly reduces the computation associated with lengthy delivery missions. The team first developed an algorithm that enables a drone to monitor aspects of its “health” in real time. With the algorithm, a drone can predict its fuel level and the condition of its propellers, cameras, and other sensors throughout a mission, and take proactive measures — for example, rerouting to a charging station — if needed.

The researchers also devised a method for a drone to efficiently compute its possible future locations offline, before it takes off. The method simplifies all potential routes a drone may take to reach a destination without colliding with obstacles.

In simulations involving multiple deliveries under various environmental conditions, the researchers found that their drones delivered as many packages as those that lacked health-monitoring algorithms — but with far fewer failures or breakdowns.

Amazon's delivery drones. Credit: Amaon
Amazon’s delivery drones. Credit: Amaon

“With something like package delivery, which needs to be done persistently over hours, you need to take into account the health of the system,” says Ali-akbar Agha-mohammadi, a postdoc in MIT’s Department of Aeronautics and Astronautics. “Interestingly, in our simulations, we found that, even in harsh environments, out of 100 drones, we only had a few failures.”

Agha-mohammadi will present details of the group’s approach in September at the IEEE/RSJ International Conference on Intelligent Robots and Systems, in Chicago. His co-authors are MIT graduate student Kemal Ure; Jonathan How, the Richard Cockburn Maclaurin Professor of Aeronautics and Astronautics; and John Vian of Boeing.

Tree of possibilities

Planning an autonomous vehicle’s course often involves an approach called Markov Decision Process (MDP), a sequential decision-making framework that resembles a “tree” of possible actions. Each node along a tree can branch into several potential actions — each of which, if taken, may result in even more possibilities. As Agha-mohammadi explains it, MDP is “the process of reasoning about the future” to determine the best sequence of policies to minimize risk.

MDP, he says, works reasonably well in environments with perfect measurements, where the result of one action will be observed perfectly. But in real-life scenarios, where there is uncertainty in measurements, such sequential reasoning is less reliable. For example, even if a command is given to turn 90 degrees, a strong wind may prevent that command from being carried out.

Instead, the researchers chose to work with a more general framework of Partially Observable Markov Decision Processes (POMDP). This approach generates a similar tree of possibilities, although each node represents a probability distribution, or the likelihood of a given outcome. Planning a vehicle’s route over any length of time, therefore, can result in an exponential growth of probable outcomes, which can be a monumental task in computing.

Agha-mohammadi chose to simplify the problem by splitting the computation into two parts: vehicle-level planning, such as a vehicle’s location at any given time; and mission-level, or health planning, such as the condition of a vehicle’s propellers, cameras, and fuel levels.

For vehicle-level planning, he developed a computational approach to POMDP that essentially funnels multiple possible outcomes into a few most-likely outcomes.

“Imagine a huge tree of possibilities, and a large chunk of leaves collapses to one leaf, and you end up with maybe 10 leaves instead of a million leaves,” Agha-mohammadi says. “Then you can … let this run offline for say, half an hour, and map a large environment, and accurately predict the collision and failure probabilities on different routes.”

He says that planning out a vehicle’s possible positions ahead of time frees up a significant amount of computational energy, which can then be spent on mission-level planning in real time. In this regard, he and his colleagues used POMDP to generate a tree of possible health outcomes, including fuel levels and the status of sensors and propellers.

Proactive delivery

The researchers combined the two computational approaches, and ran simulations in which drones were tasked with delivering multiple packages to different addresses under various wind conditions and with limited fuel. They found that drones operating under the two-pronged approach were more proactive in preserving their health, rerouting to a recharge station midmission to keep from running out of fuel. Even with these interruptions, the team found that these drones were able to deliver just as many packages as those that were programmed to simply make deliveries without considering health.

Going forward, the team plans to test the route-planning approach in actual experiments. The researchers have attached electromagnets to small drones, or quadrotors, enabling them to pick up and drop off small parcels. The team has also programmed the drones to land on custom-engineered recharge stations.

“We believe in the near future, in a lab setting, we can show what we’re gaining with this framework by delivering as many packages as we can while preserving health,” Agha-mohammadi says. “Not only the drone, but the package might be important, and if you fail, it could be a big loss.”

This work was supported by Boeing.

Source: MIT News office