Autoremove does not remove old headers

autoremove will remove any package that:

• is auto installed
• is not included in APT::NeverAutoRemove APT configuration
• don't have any dependents

Here is the debuging steps we followed

1. Checked auto/manual installation

   aptitude search '^linux* ?installed'
   

2. Checked currently declared versions under APT::NeverAutoRemove

   cat /etc/apt/apt.conf.d/01autoremove-kernels
   

3. Checked dependency

   apt-cache rdepends linux-headers-4.4.0-38-generic
   

   brings nothing but

   sudo apt-get -o Debug::pkgAutoRemove=1 -s autoremove 2> debug-autoremove.txt
   
   ...
   Following dep: virtualbox-5.0:amd64 5.0.20-106931~Ubuntu~wily Recommends linux-headers:amd64 , provided by linux-headers-4.4.0-43-lowlatency:amd64 4.4.0-43.63
   Following dep: virtualbox-5.0:amd64 5.0.20-106931~Ubuntu~wily Recommends linux-headers:amd64 , provided by linux-headers-4.4.0-43-generic:amd64 4.4.0-43.63
   Following dep: virtualbox-5.0:amd64 5.0.20-106931~Ubuntu~wily Recommends linux-headers:amd64 , provided by linux-headers-4.4.0-42-lowlatency:amd64 4.4.0-42.62
   Following dep: virtualbox-5.0:amd64 5.0.20-106931~Ubuntu~wily Recommends linux-headers:amd64 , provided by linux-headers-4.4.0-42-generic:amd64 4.4.0-42.62
   Following dep: virtualbox-5.0:amd64 5.0.20-106931~Ubuntu~wily Recommends linux-headers:amd64 , provided by linux-headers-4.4.0-38-lowlatency:amd64 4.4.0-38.57
   Following dep: virtualbox-5.0:amd64 5.0.20-106931~Ubuntu~wily Recommends linux-headers:amd64 , provided by linux-headers-4.4.0-38-generic:amd64 4.4.0-38.57
   Following dep: virtualbox-5.0:amd64 5.0.20-106931~Ubuntu~wily Recommends linux-headers:amd64 , provided by linux-headers-4.4.0-36-lowlatency:amd64 4.4.0-36.55
   Following dep: virtualbox-5.0:amd64 5.0.20-106931~Ubuntu~wily Recommends linux-headers:amd64 , provided by linux-headers-4.4.0-36-generic:amd64 4.4.0-36.55
   Following dep: virtualbox-5.0:amd64 5.0.20-106931~Ubuntu~wily Recommends linux-headers:amd64 , provided by linux-headers-4.4.0-34-lowlatency:amd64 4.4.0-34.53
   Following dep: virtualbox-5.0:amd64 5.0.20-106931~Ubuntu~wily Recommends linux-headers:amd64 , provided by linux-headers-4.4.0-34-generic:amd64 4.4.0-34.53
   Following dep: virtualbox-5.0:amd64 5.0.20-106931~Ubuntu~wily Recommends linux-headers:amd64 , provided by linux-headers-4.4.0-31-lowlatency:amd64 4.4.0-31.50
   Following dep: virtualbox-5.0:amd64 5.0.20-106931~Ubuntu~wily Recommends linux-headers:amd64 , provided by linux-headers-4.4.0-31-generic:amd64 4.4.0-31.50
   Following dep: virtualbox-5.0:amd64 5.0.20-106931~Ubuntu~wily Recommends linux-headers:amd64 , provided by linux-headers-4.4.0-28-lowlatency:amd64 4.4.0-28.47
   Following dep: virtualbox-5.0:amd64 5.0.20-106931~Ubuntu~wily Recommends linux-headers:amd64 , provided by linux-headers-4.4.0-28-generic:amd64 4.4.0-28.47
   Following dep: virtualbox-5.0:amd64 5.0.20-106931~Ubuntu~wily Recommends linux-headers:amd64 , provided by linux-headers-4.4.0-24-lowlatency:amd64 4.4.0-24.43
   Following dep: virtualbox-5.0:amd64 5.0.20-106931~Ubuntu~wily Recommends linux-headers:amd64 , provided by linux-headers-4.4.0-24-generic:amd64 4.4.0-24.43
   Following dep: virtualbox-5.0:amd64 5.0.20-106931~Ubuntu~wily Recommends linux-headers:amd64 , provided by linux-headers-4.4.0-22-lowlatency:amd64 4.4.0-22.40
   Following dep: virtualbox-5.0:amd64 5.0.20-106931~Ubuntu~wily Recommends linux-headers:amd64 , provided by linux-headers-4.4.0-22-generic:amd64 4.4.0-22.40
   Following dep: virtualbox-5.0:amd64 5.0.20-106931~Ubuntu~wily Recommends linux-headers:amd64 , provided by linux-headers-4.4.0-21-lowlatency:amd64 4.4.0-21.37
   Following dep: virtualbox-5.0:amd64 5.0.20-106931~Ubuntu~wily Recommends linux-headers:amd64 , provided by linux-headers-4.4.0-21-generic:amd64 4.4.0-21.37
   ...
   

   So it's a dependency issue through the virtual package linux-headers

I'm in doubt here, It seems to me as bug.

• Either in autoremove function, it can't deal with virtual package dependency.
• Or in virtualbox package, that may need another way to declare dependency to Linux headers.