Where Graph Theory Meets The Road: The Algorithms Behind Route Planning

April 4, 2024 by Maya Posch 32 Comments

Back in the hazy olden days of the pre-2000s, navigating between two locations generally required someone to whip out a paper map and painstakingly figure out the most optimal route between those depending on the chosen methods of transport. For today’s generations no such contrivances are required, with technology having obliterated even the a need to splurge good money on a GPS navigation device and annual map updates.

These days, you get out a computing device, open Google Maps or equivalent, ask it how you should travel somewhere, and most of the time the provided route will be the correct one, including the fine details such as train platform and departure times. Yet how does all of this seemingly magical route planning technology work? It’s often assumed that Dijkstra’s algorithm, or the A* graph traversal algorithm is used, but the reality is that although these pure graph theory algorithms are decidedly influential, they cannot be applied verbatim to the reality of graph traversal between destinations in the physical world.

Continue reading “Where Graph Theory Meets The Road: The Algorithms Behind Route Planning” →

Amazon’s ‘Just Walk Out’ Shopping Is Out, Moves To Dash Carts At Its Grocery Stores

April 4, 2024 by Maya Posch 60 Comments

After a few years of Amazon promoting a grocery shopping experience without checkout lines and frustrating self-checkout experiences, it is now ditching its Just Walk Out technology. Conceptualized as a store where you can walk in, grab the items you need and walk out with said items automatically charged to your registered payment method, it never really caught much traction. More recently it was revealed that the technology wasn’t even as automated as portrayed, with human workers handling much of the tedium behind the scenes. This despite claims made by Amazon that it was all powered by deep machine learning and generative AI.

An Amazon Dash Cart's user interface, with scanner and display. (Credit: Amazon) — An Amazon Dash Cart’s user interface, with scanner and display. (Credit: Amazon)

Instead of plastering the ceilings of stores full with cameras, it seems that Amazon instead wishes to focus on smart shopping carts that can keep track of what has been put inside them. These so-called Dash Carts are equipped with cameras and other sensors to scan barcodes on items, as well as weigh unlabeled items (like fruit), making them into somewhat of a merging of scales at the vegetable and fruit section of stores today, and the scanning tools offered at some grocery stores to help with self-checkout.

As the main problem with the Just Walk Out technology was that it required constant (700 out of 1,000 sales in 2022) human interaction, it will be interesting to see whether the return to a more traditional self-service and self-checkout model (albeit with special Dash Lanes) may speed things along. Even so, as Gizmodo notes, Amazon will still keep the Just Walk Out technology running across locations in the UK and elsewhere. Either this means the tech isn’t fully dead yet, or we will see a revival at some point in time.

The printer's display with the exploit-loaded animation playing, saying "hacked by blasty" and a bunch more stuff

A Fun Exploit For Canon Printers Brings GDB Gifts

April 4, 2024 by Arya Voronova 12 Comments

Modern printers make it all that much more tempting to try and hack them — the hardware generally tends to be decent, but the firmware appears to be designed to squeeze as much money out of you as possible while keeping your annoyance level consistently high. That’s why it’s nice to see this exploit of the Canon imageCLASS MF74XCdw series (MF742Cdw/MF743Cdw) by [blasty], triggerable over a network connection, with a story for our amusement.

In this post, we get a tale of how this hack came out of a Pwn2Own Toronto challenge, notes on the hardware involved, and we’re shown the journey to a successful hack. The Canon printer OS is built without many of the protections, which makes playing with it easier than with more modernized targets, but it’s nevertheless not straightforward. Still, exploiting a couple things like the SOAP XML implementation and the UTF8 encoder nets you an ability to play nice animations on the display, and most certainly, control over the entirety of the hardware if you wanted it.

One of the most fun things about this hack is the GDB stub recently included in the repo. If you wanted to debug Canon printers for fun or profit, [blasty] brings you a GDB stub to do that comfortably, with a respectable README that even has porting notes for other Canon ImageCLASS printer models, should you lay your hands on a different machine of despair. WiFi connectivity appears to be enough for this hack, so you better make sure you don’t have your network-connected printers exposed on the Internet — not that you needed more reasons to avoid that.