@rbalint about your test case: I wonder why linux-image-4.8.0-53-generic was not removed by u-u? Was it the booted kernel? You also did not run 'sudo /etc/kernel/postinst.d/apt-auto-removal' before running u-u. Your test case does not show how the kernels were installed. In the following, I show the extraction of terminal output of a more complete test case for u-u. It installs linux-image-extra-4.4.0-141-generic by apt. Output of 'apt autoremove --simulate' shows it would remove the kernel, and one unneeded package that is not a kernel related. Whereas u-u just removes the kernel (which may be the expected behavior). $ set -x; sudo apt install -y unattended-upgrades/xenial-proposed linux-image-extra-4.4.0-141-generic; sudo apt-mark auto linux-image-extra-4.4.0-141-generic; sudo /etc/kernel/postinst.d/apt-auto-removal; apt autoremove --simulate; sudo unattended-upgrade -v; set +x + sudo apt install -y unattended-upgrades/xenial-proposed linux-image-extra-4.4.0-141-generic Reading package lists... Done Building dependency tree Reading state information... Done unattended-upgrades is already the newest version (1.1ubuntu1.18.04.7~16.04.2). Selected version '1.1ubuntu1.18.04.7~16.04.2' (Ubuntu:16.04/xenial-proposed [all]) for 'unattended-upgrades' The following package was automatically installed and is no longer required: xscreensaver-data Use 'sudo apt autoremove' to remove it. Suggested packages: fdutils linux-doc-4.4.0 | linux-source-4.4.0 linux-tools linux-headers-4.4.0-141-generic The following NEW packages will be installed: linux-image-4.4.0-141-generic linux-image-extra-4.4.0-141-generic 0 upgraded, 2 newly installed, 0 to remove and 0 not upgraded. Need to get 58,7 MB of archives. After this operation, 224 MB of additional disk space will be used. Get:1 http://ubuntu.mirror.true.nl/ubuntu xenial-updates/main amd64 linux-image-4.4.0-141-generic amd64 4.4.0-141.167 [22,2 MB] Get:2 http://ubuntu.mirror.true.nl/ubuntu xenial-updates/main amd64 linux-image-extra-4.4.0-141-generic amd64 4.4.0-141.167 [36,5 MB] Fetched 58,7 MB in 26s (2 233 kB/s) Selecting previously unselected package linux-image-4.4.0-141-generic. (Reading database ... 332942 files and directories currently installed.) Preparing to unpack .../linux-image-4.4.0-141-generic_4.4.0-141.167_amd64.deb ... Examining /etc/kernel/preinst.d/ run-parts: executing /etc/kernel/preinst.d/intel-microcode 4.4.0-141-generic /boot/vmlinuz-4.4.0-141-generic Done. Unpacking linux-image-4.4.0-141-generic (4.4.0-141.167) ... Selecting previously unselected package linux-image-extra-4.4.0-141-generic. Preparing to unpack .../linux-image-extra-4.4.0-141-generic_4.4.0-141.167_amd64.deb ... Unpacking linux-image-extra-4.4.0-141-generic (4.4.0-141.167) ... Setting up linux-image-4.4.0-141-generic (4.4.0-141.167) ... Running depmod. update-initramfs: deferring update (hook will be called later) Examining /etc/kernel/postinst.d. run-parts: executing /etc/kernel/postinst.d/apt-auto-removal 4.4.0-141-generic /boot/vmlinuz-4.4.0-141-generic run-parts: executing /etc/kernel/postinst.d/dkms 4.4.0-141-generic /boot/vmlinuz-4.4.0-141-generic Error! Your kernel headers for kernel 4.4.0-141-generic cannot be found. Please install the linux-headers-4.4.0-141-generic package, or use the --kernelsourcedir option to tell DKMS where it's located Error! Your kernel headers for kernel 4.4.0-141-generic cannot be found. Please install the linux-headers-4.4.0-141-generic package, or use the --kernelsourcedir option to tell DKMS where it's located run-parts: executing /etc/kernel/postinst.d/initramfs-tools 4.4.0-141-generic /boot/vmlinuz-4.4.0-141-generic update-initramfs: Generating /boot/initrd.img-4.4.0-141-generic run-parts: executing /etc/kernel/postinst.d/pm-utils 4.4.0-141-generic /boot/vmlinuz-4.4.0-141-generic run-parts: executing /etc/kernel/postinst.d/unattended-upgrades 4.4.0-141-generic /boot/vmlinuz-4.4.0-141-generic run-parts: executing /etc/kernel/postinst.d/update-notifier 4.4.0-141-generic /boot/vmlinuz-4.4.0-141-generic run-parts: executing /etc/kernel/postinst.d/zz-update-grub 4.4.0-141-generic /boot/vmlinuz-4.4.0-141-generic Generating grub configuration file ... Found linux image: /boot/vmlinuz-4.15.0-46-generic Found initrd image: /boot/initrd.img-4.15.0-46-generic Found linux image: /boot/vmlinuz-4.4.0-143-generic Found initrd image: /boot/initrd.img-4.4.0-143-generic Found linux image: /boot/vmlinuz-4.4.0-141-generic Found initrd image: /boot/initrd.img-4.4.0-141-generic Found memtest86+ image: /memtest86+.elf Found memtest86+ image: /memtest86+.bin Found Ubuntu 16.04.1 LTS (16.04) on /dev/sdc2 done Setting up linux-image-extra-4.4.0-141-generic (4.4.0-141.167) ... run-parts: executing /etc/kernel/postinst.d/apt-auto-removal 4.4.0-141-generic /boot/vmlinuz-4.4.0-141-generic run-parts: executing /etc/kernel/postinst.d/dkms 4.4.0-141-generic /boot/vmlinuz-4.4.0-141-generic Error! Your kernel headers for kernel 4.4.0-141-generic cannot be found. Please install the linux-headers-4.4.0-141-generic package, or use the --kernelsourcedir option to tell DKMS where it's located Error! Your kernel headers for kernel 4.4.0-141-generic cannot be found. Please install the linux-headers-4.4.0-141-generic package, or use the --kernelsourcedir option to tell DKMS where it's located run-parts: executing /etc/kernel/postinst.d/initramfs-tools 4.4.0-141-generic /boot/vmlinuz-4.4.0-141-generic update-initramfs: Generating /boot/initrd.img-4.4.0-141-generic run-parts: executing /etc/kernel/postinst.d/pm-utils 4.4.0-141-generic /boot/vmlinuz-4.4.0-141-generic run-parts: executing /etc/kernel/postinst.d/unattended-upgrades 4.4.0-141-generic /boot/vmlinuz-4.4.0-141-generic run-parts: executing /etc/kernel/postinst.d/update-notifier 4.4.0-141-generic /boot/vmlinuz-4.4.0-141-generic run-parts: executing /etc/kernel/postinst.d/zz-update-grub 4.4.0-141-generic /boot/vmlinuz-4.4.0-141-generic Generating grub configuration file ... Found linux image: /boot/vmlinuz-4.15.0-46-generic Found initrd image: /boot/initrd.img-4.15.0-46-generic Found linux image: /boot/vmlinuz-4.4.0-143-generic Found initrd image: /boot/initrd.img-4.4.0-143-generic Found linux image: /boot/vmlinuz-4.4.0-141-generic Found initrd image: /boot/initrd.img-4.4.0-141-generic Found memtest86+ image: /memtest86+.elf Found memtest86+ image: /memtest86+.bin Found Ubuntu 16.04.1 LTS (16.04) on /dev/sdc2 done + sudo apt-mark auto linux-image-extra-4.4.0-141-generic linux-image-extra-4.4.0-141-generic set to automatically installed. + sudo /etc/kernel/postinst.d/apt-auto-removal + apt autoremove --simulate NOTE: This is only a simulation! apt-get needs root privileges for real execution. Keep also in mind that locking is deactivated, so don't depend on the relevance to the real current situation! Reading package lists... Done Building dependency tree Reading state information... Done The following packages will be REMOVED: linux-image-4.4.0-141-generic linux-image-extra-4.4.0-141-generic xscreensaver-data 0 upgraded, 0 newly installed, 3 to remove and 1 not upgraded. Remv linux-image-extra-4.4.0-141-generic [4.4.0-141.167] Remv linux-image-4.4.0-141-generic [4.4.0-141.167] Remv xscreensaver-data [5.34-2ubuntu1] + sudo unattended-upgrade -v Initial blacklisted packages: Initial whitelisted packages: Starting unattended upgrades script Allowed origins are: o=Ubuntu,a=xenial, o=Ubuntu,a=xenial-security, o=UbuntuESM,a=xenial Removing unused kernel packages: linux-image-4.4.0-141-generic linux-image-extra-4.4.0-141-generic (Reading database ... 338562 files and directories currently installed.) Removing linux-image-extra-4.4.0-141-generic (4.4.0-141.167) ... run-parts: executing /etc/kernel/postinst.d/apt-auto-removal 4.4.0-141-generic /boot/vmlinuz-4.4.0-141-generic run-parts: executing /etc/kernel/postinst.d/dkms 4.4.0-141-generic /boot/vmlinuz-4.4.0-141-generic Error! Your kernel headers for kernel 4.4.0-141-generic cannot be found. Please install the linux-headers-4.4.0-141-generic package, or use the --kernelsourcedir option to tell DKMS where it's located Error! Your kernel headers for kernel 4.4.0-141-generic cannot be found. Please install the linux-headers-4.4.0-141-generic package, or use the --kernelsourcedir option to tell DKMS where it's located run-parts: executing /etc/kernel/postinst.d/initramfs-tools 4.4.0-141-generic /boot/vmlinuz-4.4.0-141-generic update-initramfs: Generating /boot/initrd.img-4.4.0-141-generic run-parts: executing /etc/kernel/postinst.d/pm-utils 4.4.0-141-generic /boot/vmlinuz-4.4.0-141-generic run-parts: executing /etc/kernel/postinst.d/unattended-upgrades 4.4.0-141-generic /boot/vmlinuz-4.4.0-141-generic run-parts: executing /etc/kernel/postinst.d/update-notifier 4.4.0-141-generic /boot/vmlinuz-4.4.0-141-generic run-parts: executing /etc/kernel/postinst.d/zz-update-grub 4.4.0-141-generic /boot/vmlinuz-4.4.0-141-generic Generating grub configuration file ... Found linux image: /boot/vmlinuz-4.15.0-46-generic Found initrd image: /boot/initrd.img-4.15.0-46-generic Found linux image: /boot/vmlinuz-4.4.0-143-generic Found initrd image: /boot/initrd.img-4.4.0-143-generic Found linux image: /boot/vmlinuz-4.4.0-141-generic Found initrd image: /boot/initrd.img-4.4.0-141-generic Found memtest86+ image: /memtest86+.elf Found memtest86+ image: /memtest86+.bin Found Ubuntu 16.04.1 LTS (16.04) on /dev/sdc2 done Removing linux-image-4.4.0-141-generic (4.4.0-141.167) ... Examining /etc/kernel/prerm.d. run-parts: executing /etc/kernel/prerm.d/dkms 4.4.0-141-generic /boot/vmlinuz-4.4.0-141-generic Examining /etc/kernel/postrm.d . run-parts: executing /etc/kernel/postrm.d/initramfs-tools 4.4.0-141-generic /boot/vmlinuz-4.4.0-141-generic update-initramfs: Deleting /boot/initrd.img-4.4.0-141-generic run-parts: executing /etc/kernel/postrm.d/zz-update-grub 4.4.0-141-generic /boot/vmlinuz-4.4.0-141-generic Generating grub configuration file ... Found linux image: /boot/vmlinuz-4.15.0-46-generic Found initrd image: /boot/initrd.img-4.15.0-46-generic Found linux image: /boot/vmlinuz-4.4.0-143-generic Found initrd image: /boot/initrd.img-4.4.0-143-generic Found memtest86+ image: /memtest86+.elf Found memtest86+ image: /memtest86+.bin Found Ubuntu 16.04.1 LTS (16.04) on /dev/sdc2 done The link /vmlinuz is a damaged link Removing symbolic link vmlinuz you may need to re-run your boot loader[grub] The link /initrd.img is a damaged link Removing symbolic link initrd.img you may need to re-run your boot loader[grub] Packages that were successfully auto-removed: linux-image-4.4.0-141-generic linux-image-extra-4.4.0-141-generic Packages that are kept back: No packages found that can be upgraded unattended and no pending auto-removals + set +x