Command not found consumes lots of memory and CPU for longer input

Bug #576590 reported by Daniel Richard G. on 2010-05-06
32
This bug affects 6 people
Affects Status Importance Assigned to Milestone
command-not-found
High
Unassigned
command-not-found (Ubuntu)
Undecided
Unassigned

Bug Description

Binary package hint: command-not-found

This concerns command-not-found 0.2.40ubuntu5 in Ubuntu Lucid.

Once upon a time, I was working on my shiny new Lucid system, when things suddenly became very slow. I ran top(1) to check what was going on, and saw this:

top - 13:34:17 up 15 min, 5 users, load average: 3.79, 1.41, 0.54
Tasks: 158 total, 2 running, 156 sleeping, 0 stopped, 0 zombie
Cpu(s): 0.6%us, 1.5%sy, 0.0%ni, 15.8%id, 82.1%wa, 0.0%hi, 0.0%si, 0.0%st
Mem: 3917500k total, 3890004k used, 27496k free, 480k buffers
Swap: 4200956k total, 1919184k used, 2281772k free, 50180k cached

  PID USER PR NI VIRT RES SHR S %CPU %MEM TIME+ COMMAND
 2348 userme 20 0 4618m 3.2g 440 D 3 86.7 0:06.95 python
 2370 userme 20 0 11000 1308 956 S 1 0.0 0:00.03 top
 1587 root 20 0 101m 5788 1524 S 0 0.1 0:04.48 Xorg

Python was going out of control! What was it doing?

# ps uww 2348
USER PID %CPU %MEM VSZ RSS TTY STAT START TIME COMMAND
userme 2348 6.5 84.6 4729240 3316468 tty1 D 13:32 0:07 /usr/bin/python /usr/lib/command-not-found -- mmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmm...

(The m's went on for like two or three screens.)

Now, I have no idea what caused this bizarre invocation of c-n-f. (I don't typically sleep with my forehead on the keyboard or anything.) However, I copied-and-pasted the complete invocation as reported by ps(1) into a script, and tried running it:

$ time -p sh c-n-f-bug.sh
mmmm[...]mmmm: command not found
real 42.60
user 39.17
sys 1.10

During that time, c-n-f used over a gigabyte of memory. That's not right!

I am attaching the c-n-f-bug.sh script. Interestingly, it is exactly 4096 bytes long, which suggests to me that the original command invocation may have been even longer and not reported in full simply due to ps(1) limiting the output.

Daniel Richard G. (skunk) wrote :
Zygmunt Krynicki (zyga) wrote :

This is caused by spellchecker that goes out of control and creates permutations of your long command in search for similar commands

Changed in command-not-found:
status: New → Confirmed
importance: Undecided → High
Zygmunt Krynicki (zyga) on 2010-05-06
summary: - Pigs out on CPU and memory with overlong input
+ Command not found consumes lots of memory and CPU for longer input
T L R (tlr) on 2010-05-07
Changed in command-not-found (Ubuntu):
status: New → Confirmed

I temporarily fixed my own installation of cnf by changing line 89 of /usr/lib/command-not-found from:
    if len(args) == 1:
to
    if len(args) == 1 and len(args[0])<100:

That means cnf will not do anything for commands longer than 100 characters. But seriously, can anyone tell me a command that has 100 characters?

This bug can be used by an attacker to bring down a system to its knees.

selva (selvam141) on 2013-09-12
Changed in command-not-found:
status: Confirmed → Fix Released
Changed in command-not-found (Ubuntu):
status: Confirmed → Fix Released
Håkon A. Hjortland (post-hakn) wrote :
Download full text (4.6 KiB)

The bug still exists in Ubuntu 16.04.

The examples below use a 1 GB memory limit.
3000-character input: 17 seconds, no crash.
4000-character input: 0.8 seconds, MemoryError crash.

$ (ulimit -v 1000000; time /usr/lib/command-not-found -- "$(python -c 'print "x"*3000')")
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...

Read more...

To post a comment you must log in.
This report contains Public information  Edit
Everyone can see this information.

Other bug subscribers

Bug attachments